模板
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10; int tree[maxn],a[maxn],n; vector <int> vc; int getid(int x) { return lower_bound(vc.begin(),vc.end(),x)-vc.begin()+1; } int lowbit(int x) { return x&(-x); } void Ins(int pos,int y) { for(int i=pos;i<=n;i+=lowbit(i)) tree[i] += y; } int Sum(int pos) { int ans = 0; for(int i=pos;i>0;i-=lowbit(i)) ans += tree[i]; return ans; } int main(void) { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); vc.push_back(a[i]); } sort(vc.begin(),vc.end()); vc.erase(unique(vc.begin(),vc.end()),vc.end()); int ans = 0;// 逆序数 for(int i=1;i<=n;i++) { Ins(getid(a[i]),1); ans += i-Sum(a[i]); } printf("%d\n",ans); return 0; }
