开发笔记:树状数组之精灵魔法

题目

思路

很明显的求逆序对

• 可以用归并排序


• 可以用树状数组
  树状数组记得加离散化！

代码


#include
using namespace std;
const int maxn=1e5+10;
long long n;
int c[maxn];
void add(int x,int y){
for(;x<=n;x+=x&-x)c[x]+=y;
}
int ask(int x){
int ans=0;
for(;x;x-=x&-x)ans+=c[x];
return ans;
}
struct node{
long long x,v;
}wl[maxn],wl2[maxn];
bool cmp(node a,node b){
return a.x}
bool comp(node a,node b){
return a.v}
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&wl[i].x);
wl2[i].x=wl[i].x;
}
for(int i=1;i<=n;i++){
scanf("%lld",&wl[i].v);
wl2[i].v=wl[i].v;
}
sort(wl+1,wl+1+n,comp);
sort(wl2+1,wl2+1+n,comp);
int vx=1;wl[1].v=1;
for(int i=2;i<=n;i++){
if(wl2[i].v==wl2[i-1].v){
wl[i].v=wl[i-1].v;
}
else{
vx++;
wl[i].v=vx;
}
}
sort(wl+1,wl+1+n,cmp);
long long ans=0;
for(int i=n;i;i--){
ans+=ask(wl[i].v-1);
add(wl[i].v,1);
}
printf("%lld
",ans);
}