关于求逆序对总结

for循环遍历求解

这位是最简单也是时间复杂度最大的方法。

#include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; int a[n]; for(int i=0; i<n; i++){ cin >> a[i]; } int count = 0; for(int i=0; i<n-1; i++){ for(int j=i+1; j<n; j++){ if(a[i] > a[j]) count++; } } cout << count << endl; }

归并排序求解

利用分治思想，不断将数组分为两半，分别排序后在合并。

在排序期间可将逆序对求出。

#include<bits/stdc++.h> using namespace std; const int MAXN = 5e5+5; int A[MAXN]; int n; long long ans = 0; void merge_sort(int l,int r){ if(l >= r) return;//只有一个元素，不需要排序 int mid = (l + r)/2; merge_sort(l,mid); merge_sort(mid+1,r); vector<int> buf; int x = l,y = mid + 1; while(x <= mid || y <= r){//还没有放入buf的元素 //A[x]先放入buf，A[x] <= A[y]，A[y]已经没有了 if(y > r || (x <= mid && A[x] <= A[y])){ buf.push_back(A[x]);//可简化为 buf.push_back(A[x++]) x++; }else{ buf.push_back(A[y]); y++; ans += mid+1-x;//A[x]>A[y],记录逆序对个数 } } for(int i = l;i <= r;++i) A[i] = buf[i-l]; } int main(){ cin >> n; for(int i = 1;i <= n;++i) cin >> A[i]; merge_sort(1,n); /*--------------输出排序后的数组--------------*/ for(int i = 1;i <= n;++i) cout << A[i] << " "; /*--------------输出逆序对的个数--------------*/ cout << ans << endl; return 0; }

树状数组求解

求逆序对即求每个数i之前有多少比他大的数（设为bi），建立c数组后边转化为如何快速求c数组的区间和

1.数据离散化：99 5 35 --> 3 1 2

2.建立c[i]数组：c[i]代表当前值为i的数的个数，c数组不断统计a[i]并计算bi

3.快速求c数组的区间和：利用树状数组实现

关于lowbit（）函数：返回二进制最后一个1与其后面的0.

#include<bits/stdc++.h> using namespace std; const int MAXN = 5*1e5+5; struct Node{ int num,id,newnum; }nodes[MAXN]; int N; int a[MAXN]; bool cmp1(const Node &a,const Node &b){ return a.num < b.num; } bool cmp2(const Node &a,const Node &b){ return a.id < b.id; } int lowbit(int x){ return x&-x; } void add(int x,int v){ while(x<=N){ a[x] += v; x += lowbit(x); } } int ask(int x){ int ans = 0; while(x){ ans += a[x]; x -= lowbit(x); } return ans; } int main(){ /*------------------存储数据------------------*/ scanf("%d",&N); for(int i = 1;i <= N;i++){ scanf("%d",&nodes[i].num);//记录数据 nodes[i].id = i;//记录数据的存储顺序 } /*----------------数据的离散化----------------*/ sort(nodes+1,nodes+N+1,cmp1);//按照数据大小排序 int cnt = 0; for(int i = 1;i <= N;i++){ if(nodes[i].num != nodes[i-1].num) cnt++; nodes[i].newnum = cnt; } sort(nodes+1,nodes+N+1,cmp2);//按照存储顺序排序，恢复原次序 /*-------------树状数组维护区间和-------------*/ long long ans = 0; for(int i = 1;i <= N;i++){ add(nodes[i].newnum,1); ans += ask(N) - ask(nodes[i].newnum); } printf("%lld",ans); return 0; }