codeforces 459D - Pashmak and Parmida's problem【离散化+处理+逆序对】

比眉伴天荒 2022-08-11 03:59 135阅读 0赞

题目：[codeforces 459D - Pashmak and Parmida's problem][codeforces 459D - Pashmak and Parmida_s problem]

题意：给出n个数ai，然后定义*f*(*l*, *r*, *x*) 为ak = x，且l<=k<=r，的k的个数，求*i*, *j*(1 ≤ *i* < *j* ≤ *n*) ，*f*(1, *i*, *a**i*) > *f*(*j*, *n*, *a**j*).，有多少对满足条件的i，j。

分类：逆序数，线段树，离散化，

分析：这是一道不错的数据结构题目，比较灵活。推一下第一组样例之后发现时让求一个逆序数的题目，但是不是单纯的求逆序数。

第一组样例：

1 2 1 1 2 2 1

然后我们按数的出现的次数从前往后编号，得到：

1 1 2 3 2 3 4

在从后往前编号：得到

4 3 3 2 2 1 1

然后我们从第二组数中的数在第一组数中找逆序对就是ans。

当前给出的数是1e-9次方，所以要先离散化一次，然后可以用线段树求逆序数的方法就ok。要注意的是ans会超int

代码：

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <map>
    using namespace std;
    const int N = 1001000;
    int a[N],b[N],c[N],sum[N];
    struct Node
    {
        int l,r,num;
    };
    Node tree[4*N];
    map<int,int> m1,m2;
    void build(int l,int r,int o)
    {
        tree[o].l=l,tree[o].r=r;
        tree[o].num=0;
        if(l==r)
            return ;
        int mid=(l+r)>>1;
        build(l,mid,o<<1);
        build(mid+1,r,o+o+1);
    }
    void update(int t,int o)
    {
        if(tree[o].l==tree[o].r && tree[o].l==t)
        {
            tree[o].num++;
            return ;
        }
        int mid=(tree[o].l+tree[o].r)>>1;
        if(t>mid)
            update(t,o+o+1);
        else
            update(t,o+o);
        tree[o].num=tree[o+o].num+tree[o+o+1].num;
    }
    int query(int l,int r,int o)
    {
        //printf("%d %d %d %d\n",l,r,tree[o].l,tree[o].r);
        if(tree[o].l==l && tree[o].r==r)
        {
            return tree[o].num;
        }
        int mid=(tree[o].l+tree[o].r)>>1;
        if(r<=mid)
            return query(l,r,o+o);
        else if(l>mid)
            return query(l,r,o+o+1);
        else
            return query(l,mid,o*2)+query(mid+1,r,o*2+1);
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int n;
        while(~scanf("%d",&n))
        {
            for(int i=0;i<n;i++)
                scanf("%d",&a[i]);
            int cnt=1;
            for(int i=0;i<n;i++)  //离散化
            {
                if(!m1[a[i]])
                    m1[a[i]]=cnt++;
                a[i]=m1[a[i]];
            }
            cnt = 0;
            memset(sum,0,sizeof(sum));
            for(int i=0;i<n;i++)
            {
                sum[a[i]]++;
                b[i]=sum[a[i]];
                cnt=max(cnt,b[i]);
            }
            memset(sum,0,sizeof(sum));
            for(int i=n-1;i>=0;i--)
            {
                sum[a[i]]++;
                c[i]=sum[a[i]];
            }
            build(1,cnt,1);
            long long ans=0;
            for(int i=0;i<n;i++)
            {
                if(c[i]<cnt)
                    ans+=query(c[i]+1,cnt,1);
                update(b[i],1);
            }
            printf("%lld\n",ans);
            m1.clear();
            m2.clear();
        }
        return 0;
    }

[codeforces 459D - Pashmak and Parmida_s problem]: http://codeforces.com/problemset/problem/459/D