题目：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，如需转载请自行联系原作者
