杂谈逆序对
摘要：逆序对有多种求法，线段树，树状数组，归并排序，trie树等，笔者在这里就介绍三种解法。
001 归并排序
归并排序求逆序对的原理基于排序过程。归并排序过程中在做merge操作时，会从左右两边选较小的值在前方进行合并，由此操作，我们可以知晓，在合并左右数组时，如果选取的是右半部分的值，也就是说右半部分的被选值小于左边的，那么，我们就可以知晓，此处存在逆序对，对答案应该产生贡献。假设左指针为left，右指针为right，而分割左右两边的节点为mid，那么此使产生的贡献ops=mid-left+1就是左半部分中比右半部分选定值小的数的个数。此处有一个小细节需要注意，就是在常规归并排序中，选值时，左半部分的那一部分可以写小于号，也可以写小于等于号，但是在求逆序对时，由于相等一般不考虑为逆序对，因此此处应保证写的是小于等于号。
具体代码实现：
#include<bits/stdc++.h> using namespace std; const int N=5e5+5; int a[N],n; long long ans=0; void merge(int l,int mid,int r) {int left=l;int right=mid+1;queue<int>q;while(left<=mid&&right<=r){if(a[left]<=a[right]) q.push(a[left++]);else q.push(a[right++]),ans+=mid-left+1;}while(left<=mid) q.push(a[left++]);while(right<=r) q.push(a[right++]);for(int i=l;i<=r;i++) a[i]=q.front(),q.pop(); } void mergesort(int left,int right) {if(left>=right) return;int mid=(left+right)>>1;mergesort(left,mid);mergesort(mid+1,right);merge(left,mid,right); } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n;for(int i=1;i<=n;i++)cin>>a[i];mergesort(1,n);cout<<ans<<endl;return 0; }
002 树状数组
关于树状数组基础
树状数组求逆序对的原理，在树状数组中存储的是排名，每次操作做的是查询对应x在树状数组中的排名。从而得到rank，以便累计答案。
#include<bits/stdc++.h> using namespace std; const int N=5e5+5; long long n,ans=0,c[N]; void add(int x,int y,int n) {for(;x<=n;x+=(x&-x) ) c[x]+=y; } long long query(int x) {long long ans=0;for(;x;x-=(x&-x)) ans+=c[x];return ans; } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n;vector<int >a(n);for(int i=0;i<n;i++)cin>>a[i];vector<int> sa=a;sort(sa.begin(),sa.end());sa.erase(unique(sa.begin(),sa.end()),sa.end());int m=int(sa.size());for(int i=0;i<n;i++){int rank=int(lower_bound(sa.begin(),sa.end(),a[i])-sa.begin())+1;int less_rank=query(rank);ans+=i-less_rank;add(rank,1,m);}cout<<ans<<endl;return 0; }
//注意：开vector的时候要注意vector的使用规则，当需要使用cin或者scanf而不是push_back将值加入vector时，我们需要开出动态数组的地址空间，不然就会因为程序访问不存在的地址空间而导致程序异常崩溃，而且，这种错误根本不会报错！
003 pbds
考虑求逆序对的本质，查询排名+贡献，非常符合平衡树的使用场景，然而，使用平衡树解决这种问题无异于是大炮打蚊子，因此提供一种pbds的解法，以供参考。
#include<bits/stdc++.h> using namespace std; #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define int long long using namespace __gnu_pbds; int n,ans; tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> tr;signed main(){cin.tie(0)->sync_with_stdio(0);cin>>n;for(int i=1,x;i<=n;i++){cin>>x;ans+=tr.order_of_key({-x,0});tr.insert({-x,i});}cout<<ans;return 0; }