题目：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;

}