P1908 逆序对

FDOI · 2025-03-16 18:34:40 · 个人记录

思路

题目要求求出序列中所有的逆序对个数，可以转换为求每个数所有的逆序对个数之和，算单点贡献。

转化：

转化为取一个数，将这个数后面的所以数的个数记录，若这个数后面有小于它本身的数，那么答案加一。

这时就运用到区间查询功能了，考虑使用树状数组。

树状数组：

在树状数组中存储桶排结果，当然存是在这个数后面的桶排结果，并且加入树状数组，加入等价于区间加一。

此后查询区间 1 到 a_{i}-1 的所有值，即可得出答案。

由于本题数据较大，桶排需要离散化。

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=7e5+5;
map<int,int>mp;
int n,a[N],b[N],c[N];
int cnt;
int lowbit(int x){
    return x&(-x);
}
void add(int x){
    while(x<=n){
        c[x]+=1;
        x+=lowbit(x);
    }
}
int get(int x){
    int ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
signed main(){
//  freopen("P1908_11.in","r",stdin);
//  freopen("P1908.txt","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(a+1,a+n+1);
    int len=unique(a+1,a+n+1)-a-1;
    for(int i=1;i<=len;i++){
        mp[a[i]]=i;
    }
    for(int i=n;i>=1;i--){
        add(mp[b[i]]);
        cnt+=get(mp[b[i]]-1);
        //cout<<cnt<<endl;
    }
    cout<<cnt;
    return 0;
}