P1908 题解

ikunTLE · 2025-04-04 00:00:17 · 题解

这里讲一下树状数组求逆序对，不会树状数组推荐一下我的题解。

思路

将所有数离散化，因为逆序对数量只关心数的相对大小（同时离散化后用树状数组易存储）。

可以将求逆序对的过程理解为对于每个点前面有多少个点比它大。那么每处理到一个数，就可以算 1 到 a_i-1 有多少个数；算完后将 1 到 a_i 都增加 1 表示前缀中出现次数。

不难发现可以实现上述区间求和、单点修改的可以用树状数组。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=5e5+10;
int n,a[N],c[N];
int lowbit(int x){
    return x&(-x);
}
void add(int x,int num=1){
    while(x<=n){
        c[x]+=num;
        x+=lowbit(x);
    }
    return;
}
long long sum(int x){
    long long res=0;
    while(x){
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
int main(){
    n=read();
    vector<int>vc;
    for(int i=1;i<=n;++i){
        a[i]=read();
        vc.push_back(a[i]);
    }
    sort(vc.begin(),vc.end());
    vc.erase(unique(vc.begin(),vc.end()),vc.end());
    for(int i=1;i<=n;++i)
        a[i]=lower_bound(vc.begin(),vc.end(),a[i])-vc.begin()+1;
    long long ans=0;
    for(int i=n;i>=1;--i){
        ans+=sum(a[i]-1);
        add(a[i]);
    }
    printf("%lld\n",ans);
    return 0;
}