谈一下树状数组怎么求逆序数,主要是记录用的,大家当乐子看就行
当得到一个数组,要求其逆序数时,人工最朴素的做法就是从前往后数,看这个数前面有多少个比它大的数,最终对这些结果求和就是整个数组的逆序数
使用树状数组的原理也是这个,一边从前往后遍历数组的位置,一边记录前面的数有多少个数比这个位置上的数字要小,这个位置的逆序数就是i-qry(pos),qry是查询从1到pos的数的出现有多少个数不大于当前位置的数
要做到这个实现,我们用树状数组维护这个过程,每遍历到一个数字,我们让在pos位置加1,并更新树状数组,然后查询1~pos
接下来又有一个小细节
-
如果数组中数字的出现不是连续的,比如说不是3 1 2 4这样出现的,而是100 10 20 4000这样出现的怎么办?
我们进行离散化,输入数字时记录这个数的数值和位置,输入完之后根据数值进行排序,排序后的每个值位置依次变成1 2 3 . . . n。
上面这样处理对于重复大小的元素也能够正确处理,读者可以思考一下为什么
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=5e5+5;
struct fac{int val,pos;
}a[N];
int b[N];
int tree[N];
int n;bool cmp(fac x,fac y){if(x.val==y.val) return x.pos<y.pos;return x.val<y.val;
}int lowbit(int x){return x&-x;}void ins(int p,int x){while(p<=n){tree[p]+=x;p+=lowbit(p);}
}int qry(int p){int ret=0;while(p>=1){ret+=tree[p];p-=lowbit(p);}return ret;
}void solve(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i].val;a[i].pos=i;}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){b[a[i].pos]=i;}int ans=0;for(int i=1;i<=n;i++){ins(b[i],1);ans+=i-qry(b[i]);}cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(false);cin.tie(0);int T=1;
// cin>>T;while(T--)solve();return 0;
}