cf 61E. Enemy is weak 树状数组求逆序数(WA) 分类: Brush Mode 2014-10-19 15:16 104人阅读 评论(0) 收藏

时间:2021-09-14 22:42:05
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
long long num[1000005];
long long fz[1000005];
long long xds[1000005];
long long qs[100005];
long long hs[100005];
map <long long, int> tab;
int n, ni;
long long sum(int i)
{
long long s = 0;
while(i)
{
s+=xds[i];
i-=(-i)&i;
}
return s;
} void add(int i,long long d)
{
while(i<=n)
{
xds[i]+=d;
i+=(-i)&i;
}
} int main()
{
scanf("%I64d",&n);
for(int i=0;i<n;i++)
{
scanf("%I64d",&num[i]);
fz[i] = num[i];
}
sort(fz,fz+n);
ni = unique(fz,fz+n)-fz; for(int i=0;i<ni;i++)
{
tab[fz[i]] = i + 1;
}
for(int i=0;i<n;i++)
{
add(tab[num[i]],1);
qs[i] = sum(tab[num[i]])-1;
hs[i] = (i+1-qs[i]);
}
long long ans = 0;
for(int i=0;i<n;i++)
{
ans+=((hs[i]-1)*(tab[num[i]]-qs[i]-1));
}
printf("%I64d\n",ans);
return 0;
}

不知道哪里错了,好烦

版权声明:本文为博主原创文章,未经博主允许不得转载。