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, ai) > f(j, n, aj).，有多少对满足条件的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;
}

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5063155.html，如需转载请自行联系原作者