原题
这里有一个树状数组的做法，先离散化，由小到大排序，每枚举到一个点，就加入树状数组，然后计算之前比他大的值，加入ans。
#include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define in(x) scanf("%d",&x); using namespace std; int n,p[40001],c[40001]; struct node{ int data,mark; }a[40001]; void add(int pos,int v) { for(int i=pos;i<=n;i+=i&(-i)) c[i]+=v; } long long sum(int x) { long long anse=0; for(int i=x;i>0;i-=i&(-i)) anse+=c[i]; return anse; } int cmp(node a,node b) { return a.data<b.data; } int main() { in(n); for(int i=1;i<=n;++i) { in(a[i].data); a[i].mark=i; } sort(a+1,a+n+1,cmp); for(int i=1;i<=n;++i) p[a[i].mark]=i; long long ans=0; for(int i=1;i<=n;++i) { add(p[i],1); ans+=i-sum(p[i]); } cout<<ans; return 0; }
