逆序对3

由于我不止说了树状数组，还有权值线段树，那就来写一个吧

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+25;
struct node{
    ll l,r,sum;
};
ll n,cnt,ans;
ll a[MAXN],b[MAXN];
node sgt[MAXN<<2];
#define ls(p) p<<1
#define rs(p) p<<1|1
inline void push_up(const ll &p){
    sgt[p].sum=sgt[ls(p)].sum+sgt[rs(p)].sum;
    return;
}
inline void build(const ll &l,const ll &r,const ll &p){
    sgt[p]={l,r,0};
    if(l>=r) return;
    ll mid=l+r>>1;
    build(l,mid,ls(p));
    build(mid+1,r,rs(p));
    return;
}
inline void update(const ll &q,const ll &p,const ll &c){
    if(sgt[p].l==q&&sgt[p].r==q){
        sgt[p].sum+=c;
        return;
    }
    ll mid=sgt[p].l+sgt[p].r>>1;
    if(mid>=q) update(q,ls(p),c);
    else update(q,rs(p),c);
    push_up(p);
    return;
}
inline ll query(const ll &ql,const ll &qr,const ll &p){
    if(sgt[p].l>=ql&&sgt[p].r<=qr) return sgt[p].sum;
    ll res=0,mid=sgt[p].l+sgt[p].r>>1;
    if(mid>=ql) res=query(ql,qr,ls(p));
    if(mid<qr) res+=query(ql,qr,rs(p));
    return res;
}
#undef ls
#undef rs
int main(){
	cin>>n;
	for(ll i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	cnt=unique(b+1,b+1+n)-b-1;
    build(1,n,1);
	for(ll i=1;i<=n;i++){
		a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
		if(a[i]<n) ans+=query(a[i]+1,n,1);
		update(a[i],1,1);
	}
	cout<<ans;
	return 0;
}