树状数组55pts求助悬关

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x)&(-(x))
#define R register
#define F(i,a,b) for(int i = (a);i<=(b);i++)
using namespace std;
inline int read(){R int x=0,t=1;R char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*t;}
const int N=5e5+10;
int n,a[N],cnt,d[N],ans,q[4*N];
inline void add(int x,int y)
{
    while(x<=cnt){
        q[x]+=y;
        x+=lowbit(x);
    }
    return;
}
inline int query(int x)
{
    int sum=0;
    while(x>0){
        sum+=q[x];
        x-=lowbit(x);
    }
    return sum;
}
signed main()
{
    n=read();
    F(i,1,n) a[i]=read(),d[i]=a[i];
    sort(a+1,a+1+n);
    cnt=unique(a+1,a+1+n)-a-1;
    F(i,1,n){
        d[i]=lower_bound(a+1,a+1+n,d[i])-a;
    }
    for(int i = n;i>=1;i--){
        ans+=query(d[i]-1);
        add(d[i],1);
    }
    cout << ans << '\n';
    return 0;
}