用不同的姿势求逆序对（复习篇）
用不同的姿勢求逆序對（復習篇）
文章目錄
- 用不同的姿勢求逆序對（復習篇）
- 前言
- 講解
- 歸并排序
- 樹狀數組
- 線段樹
- 題目
- 思路
- 代碼
- 歸并排序求逆序對
- 樹狀數組求逆序對
- 線段樹求逆序對
- 歷屆試題 小朋友排隊解題代碼
前言
最近忙于小項目，感覺很久沒刷題了!
今天在藍橋上做了一個逆序對的題目（小朋友排隊 ），之前只用過歸并排序求解這類問題。
現在以現在的知識水平，新加了兩種解題姿勢。
目前我比較喜歡以多種姿勢來解一道題，因為可以順帶復習一些以前學過的知識。小聲bb一句:做題不在于多，而在于精！
逆序對的概念很簡單。當ai > aj,i < j，稱（ai,aj）為一對逆序對。
對應的還有一個正序對，解法幾乎是一致的。
直接問法（裸題）：就是給定一個序列，直接讓你求逆序對。
隱晦問法：需要根據特性來推出是求逆序對個數。如本文提到的小朋友排隊問題。
常見的解法有：
- 歸并排序
- 樹狀數組
- 線段樹
（其他高級解法目前觸及到了我的知識盲點…）
因為我是當作復習，所以本篇博客就粗略講解上面這三種解法。
（樹狀數組和線段樹解法是類似的，只是換成了不同的數據結構。）
講解
歸并排序
歸并排序基本做法是，將一個序列不斷二分，直到子序列不能再分了（只有一個元素）就進行兩兩合并。在合并過程中 優先原則（先取大的還是小的） 可以決定最終序列為升序還是降序。具體實現—》排序專欄
歸并排序是如何來求解逆序對？
關鍵就在于兩個子序列合并過程，
比如現在歸并過程中（原則：優先取大的）有兩個子序列待合并：
歸并臨時存儲數組 tmp[] = {}，逆序對數 ans = 0;
子序列1 ： 5 3
子序列2： 4 2 1
5 > 3 -----》子序列1中的5 會大于 子序列2 中的4以及它后面的所有元素，
此時可以統計到子序列2和子序列1中的5構成的逆序對數：
（5，3）（5，2），（5，1），這個對數就是此時子序列2中的元素個數。
ans += 3；tmp = {5}.
繼續合并，子序列1中的3 < 子序列2中的4:
tmp = {5,4}
子序列1中的3 > 子序列2中的2，
ans += 2
tmp = {5,4,3}
最后tmp中加上剩下子序列中沒有比較的元素：
tmp = {5,4,3,2,1}
…
樹狀數組
樹狀數組主要用于解決區間修改（一般是單點修改，區間修改要引入差分），區間查詢（一般是求區間和）的問題。
關于樹狀數組的入門題目
樹狀數組的結構（圖片來源B站目前樹狀數組Top1講解視頻）：
t[]數組用于存儲 對應位置上的a[]數組元素以及在它的部分元素 的和。
基礎性質：
- lowbit(x) = x&-x;
- t[x]維護的區間長度len = lowbit(x)
- t[x_root] = t[x+lowbit(x)]
- 單點更新：如果此時更新某個a[x],只需順著向上更新覆蓋了a[x]的區間即可。比如:a[2] += 1,則：t[2] += 1,t[4] += 1,t[8] += 1;
(ps : 2+lowbit(2) = 4,4+lowbit(4) = 8) - 區間求和：區間求和基于求解前綴和，這里的前綴和是單點更新的逆過程，比如求解前綴和sum[6],sum[6] = t[6] + t[4] ，(ps: 6 - lowbit(6) = 4)。
[l,r]區間和只需要用前綴和sum[r] - sum[l-1]即可得到。
總結了一大堆基礎知識，那么如何用樹狀數組來求解逆序對？
樸素做法：
有一個數字序列，序列中的元素可能重復。現在要求這個序列的逆序對。
比如這樣一個序列（7個元素）：
__value: 5 4 6 8 9 4 5
index(id) :1 2 3 4 5 6 7
要求逆序對數，即求每個元素的前面有多少個比它大的元素。
現在我們來想象一下：把序列元素想象成小球，id是每個小球的唯一編號。現在 在一條路上（一條線段并標有數值）有9個坑位（小球value_max = 9，坑位可以更多，但是沒有必要），
我們需要根據小球的value值將小球推到對應數值的坑里，而且每次只能推一個小球入坑（一個坑可以放很多個對應value值的小球）。現在，每次推入一個小球，就可以看一下，這條路上在即將要推入的坑后面有幾個坑是已經有小球的（之前推進去了更后面的坑，即值比當前大，這樣就構成逆序對了）。后面有小球的坑數 就是 可以和這個小球的value構成逆序對的數目。依次做下去就可以統計到這個序列的逆序對總數目。
這個例子推小球換成樹狀數組的單點更新，看后面的坑位幾個有小球 換成樹狀數組區間求和即可。
這個是很樸素的做法，所以有比較大的局限性。
當序列value值特別大的時候（比如1e9），內存可能不夠。
這時需要 將序列的值離散化，換成相對大小即可。
但是因為有value相同的元素，離散化處理起來還是有點小麻煩。
下面介紹一種更簡單的方法：
抓住逆序對是 統計 在這個數前面并且比這個樹大 的數 的數目 的特性
所以我們可以先對原序列從大到小排序，這里的排序規則需要注意一點，因為有相同的元素，所以需要增加一個規則：當元素value值相同時，需要讓元素下標（id）大的優先排序。這是為什么？
我們先看如何來處理這個排序好的序列。
現在想象有一條線段，線段上標有一系列id數值。
我們根據排好的的序列的順序，依次在線段上相應位置（線段上的id和元素id一一對應）插入元素所對應的id值（id就是原來序列的位置），
在插入前，我們可以在線段上看一下，在這個id前有多少個已經插入的元素。
這些前面的插入的元素一定時比當前元素value大的，因為我們從大到小預先排好了順序。所以這些元素的個數 就是可以和 當前即將插入的id所對應的元素 構成逆序對的數目。
現在來看一下，為什么元素value相同時，id大的優先？
因為兩個相同的元素不能構成逆序對，如果讓id小的優先插入，
那么當后面value值相同（id更大）的元素插入，統計時（以當前id向前看）
就會多統計到逆序對的數目，因為把value值相同的也算進去了。
細品一下很容易領悟到。
我覺得這種做法很精妙，不需要離散化處理即可處理很大的數據。因為這種做法只跟元素個數有關了。但是需要先排序，相對樸素做法會慢一些。
這種做法放到樹狀數組上就是單點更新，求前綴和。
初始化t[] = {0},每插入一個元素，t[id] += 1,
統計就是統計id前 1的個數。
…
線段樹
線段樹也是主要解決區間修改，區間查詢的問題。但是相比于樹狀數組，它在區間修改方面更方便，線段樹也更強大些，有各種變形。
關于線段樹的入門題目
線段樹結構（圖片來源百度圖片）：
線段樹這里不多介紹了。
線段樹做法和樹狀數組做法差不多。
在上面提到的 樹狀數組來求逆序對 的簡單做法種 ，數據結構換成線段樹，
統計時，把求前綴和換成求[1，id-1]的區間和即可。
具體實現請參考本文的代碼~
題目
用于練習的題目：
- 洛谷: P1908 逆序對
- 藍橋: 試題 歷屆試題 小朋友排隊
思路
-
洛谷: P1908 逆序對 --》 這個是裸題，直接寫即可
-
藍橋: 試題 歷屆試題 小朋友排隊 --》解題思路:
很明顯只需要統計出每個小朋友的交換次數，然后根據等比數列求和求解最終的結果。
關鍵就是如何統計每個小朋友的交換次數，從題目的只允許相鄰兩個小朋友作交換。第一時間想到排序中的：冒泡排序，歸并排序。根據題目數據范圍和時限，很快可以pass掉冒泡~（幾種排序算法性能的比較）。
確定可以用歸并排序做，再確定如何統計每個小朋友的交換次數。
我們可以知道，一個小朋友 需要和前面比他大的和后面比它小的人交換位置。
所以一個小朋友的交換次數 = 前面比他大的人數 + 后面比它小的人數
》很快可以延申到：
- 這個小朋友 前面部分 和這個小朋友 構成的逆序對；
- 這個小朋友后面 和這個小朋友構成的 正序對(把序列倒過來，也可以換成求逆序對)
為了統一處理，求解小朋友后面部分的人數時，把整個序列倒過了求解逆序對。
總之，我們要分兩次求逆序對：
確定了是求解逆序對。我們就可以根據自己的知識儲備，
采用多種姿勢來解題了~
最下方貼了一份我采用樹狀數組的求解的本題代碼，其他方法，可以根據本文中的參考代碼，適當修改一下即可。
代碼
歸并排序求逆序對
之前寫過，可以去我的 排序專欄 考考古，當時幾乎只貼了一份稚嫩的代碼。現在回想起來真不應該，后面再去認真整理…
我今天重新寫了一遍，代碼如下：
/* 歸并排序求逆序對 */ #include <iostream> using namespace std; const int N = 5e5+5; int a[N]; int b[N]; //temp long long ans; void merge_a(int l,int mid,int r) {int i = l,j = mid + 1;int k = 0; //注意b數組最好從0開始存，后面不易出錯while(i <= mid && j <= r){//從大到小排序if(a[i] > a[j]){ans += r - j + 1;b[k++] = a[i++];}else{b[k++] = a[j++];}}while(i <= mid) b[k++] = a[i++];while(j <= r) b[k++] = a[j++];for(int i = 0; i < k; i++){a[l+i] = b[i];} } void merge_sort(int l,int r) {if(l < r){int mid = (l + r) >> 1;//遞歸，不斷劃分merge_sort(l,mid);merge_sort(mid+1,r);//合并merge_a(l,mid,r);} } int main() {int n;cin>>n;for(int i = 1; i <= n; ++i){cin>>a[i];}merge_sort(1,n);cout<<ans<<endl;return 0; }樹狀數組求逆序對
/* 樹狀數組求逆序對 */ #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 5e5+5; int n; int t[N]; struct Node {int v;int id;bool operator<(const Node& x)const{if(v == x.v){return id > x.id;}return v > x.v;} }node[N]; inline int lowbit(int x) {return x&-x; }void add(int x,int v) {for(int i = x; i <= n; i+=lowbit(i)){t[i] += v;} }LL get_sum(int x) {LL sum = 0;for(int i = x; i > 0; i-=lowbit(i)){sum += t[i];}return sum; } int main() {cin>>n;for(int i = 1; i<= n; ++i){cin>>node[i].v;node[i].id = i;}sort(node+1,node+n+1);LL ans = 0;for(int i = 1; i<= n; ++i){ans += get_sum(node[i].id-1);add(node[i].id,1);}cout<<ans<<endl;return 0; }線段樹求逆序對
/* 線段樹求逆序對 */ #include <iostream> #include <cstdio> #include <algorithm> #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r using namespace std; const int N = 5e5; int sum[N<<2];struct Node {int v;int id;bool operator<(const Node &x)const{if(v == x.v) return id > x.id;return v > x.v;} } node[N];//向上更新 inline void push_up(int rt) {sum[rt] = sum[rt<<1] + sum[rt<<1|1]; }// 建樹和向下傳遞這里不需要...//單點更新 void update_point(int pos,int v,int rt,int l,int r) {if(l == r){sum[rt] += v;return;}int mid = (l + r) >> 1;if(pos <= mid) update_point(pos,v,lson);else update_point(pos,v,rson);push_up(rt); } //區間查詢 int query(int L,int R,int rt,int l,int r) {if(L > R) return 0;if(L <= l && r <= R){return sum[rt];}int mid = (l + r) >> 1;int res = 0;if(L <= mid)res += query(L,R,lson);if(R > mid)res += query(L,R,rson);return res; } int main() {int n;//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);scanf("%d",&n);for(int i = 1; i <= n; ++i){scanf("%d",&node[i].v);node[i].id = i;}sort(node+1,node+n+1);long long ans = 0;for(int i = 1; i <= n; ++i){ans += query(1,node[i].id-1,1,1,n);update_point(node[i].id,1,1,1,n);}printf("%lld\n",ans);return 0; }歷屆試題 小朋友排隊解題代碼
#include <iostream> #include <cstring> #include <algorithm> const int N = 1e5+5; typedef long long LL; using namespace std; struct Node {int val;int id;int cnt;bool operator<(const Node &x)const{if(val == x.val){return id > x.id;}return val > x.val;} } a[N]; LL b[N],t[N]; int n; inline int lowbit(int x) {return x&(-x); } void add(int x,int v) {for(int i = x; i <= n; i+= lowbit(i)){t[i] += v;}return; } LL get_sum(int x) {LL sum = 0;for(int i = x; i > 0; i-=lowbit(i)){sum += t[i];}return sum; } int main() {cin>>n;for(int i = 1; i <= n; ++i){cin>>a[i].val;a[i].id = i;}sort(a+1,a+n+1);for(int i = 1; i <= n; ++i){b[a[i].id] = get_sum(a[i].id-1); //前面比它大的add(a[i].id,1);}memset(t,0,sizeof(t));for(int i = n,j = 0; i; --i,++j){b[a[i].id] += j - get_sum(a[i].id-1); //后面比它小的add(a[i].id,1);}LL ans = 0;for(int i = 1; i <= n; ++i){ans += (1 + b[i]) * b[i] / 2;}cout<<ans<<endl;return 0; }總結
以上是生活随笔為你收集整理的用不同的姿势求逆序对（复习篇）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python 判断类是否存在某个属性或方
- 下一篇： 矩形法求定积分的原理和实现