树状数组之精灵魔法

题目

思路

很明显的求逆序对

• 可以用归并排序
• 可以用树状数组
  树状数组记得加离散化！

代码

#include<bits/stdc++.h>
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<b.x;
}
bool comp(node a,node b){
    return a.v<b.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("%lldn",ans);

}