今天写道这么一道题,鉴于不太熟悉归并和树状数组,还是用线段树水一下(
板子如下
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=5e5+10;
#define int long long
#define lc u<<1
#define rc u<<1|1
struct Tree{
int l,r,val;
}tr[N*4];
int n;
void pushup(int u){
tr[u].val=tr[lc].val+tr[rc].val;//维护个数 区间大于id的个数就是逆序对个数
}
void build(int u,int l,int r){//写成数组形式可以免掉这一段的,但是写习惯了
tr[u]={l,r};
if(l==r) return;
int m=(l+r)>>1;
build(lc,l,m);
build(rc,m+1,r);
pushup(u);
}
void update(int u,int x){
if(tr[u].l==tr[u].r){
tr[u].val++;return;
}
int m=(tr[u].l+tr[u].r)>>1;
if(x<=m) update(lc,x);
else update(rc,x);
pushup(u);
}
int query(int u,int l,int r){
if(l<=tr[u].l&&tr[u].r<=r){
return tr[u].val;
}
//cout<<1<<endl;
int m=(tr[u].l+tr[u].r)>>1;
int num=0;
if(l<=m) num+=query(lc,l,r);
if(r>m) num+=query(rc,l,r);
return num;
}
signed main(){
cin>>n;
vector<int> a(n+1);
vector<int> b(n+1);
for(int i=1;i<=n;++i) cin>>a[i],b[i]=a[i];
sort(b.begin()+1,b.begin()+1+n);
int ans=0;
int m=unique(b.begin()+1,b.begin()+1+n)-(b.begin()+1);
//离散化,这里不离散化也行,不是所有时候都会卡这里的数据
build(1,1,m);
for(int i=1;i<=n;++i){
int id=lower_bound(b.begin()+1,b.begin()+1+m,a[i])-b.begin();
update(1,id);
ans+=query(1,id+1,m);
//cout<<query(1,id+1,m)<<endl;
}
//for(int i=1;i<=n;++i) cout<<tr[i].val<<endl;
cout<<ans<<endl;
return 0;
}