概念

分治算法（Divide and Conquer）是一種解決問題的策略，它將一個問題分解成若干個規模較小的相同問題，然后遞歸地解決這些子問題，最后合并子問題的解得到原問題的解。分治算法的基本思想是將復雜問題分解成若干個較簡單的子問題，然后逐個解決這些子問題，最后將子問題的解合并得到原問題的解。

分治算法的基本步驟如下：

1. 分解（Divide）：將原問題分解成若干個規模較小的相同問題。這些子問題應該是相互獨立的，即解決一個子問題不會影響其他子問題的解。

2. 解決（Conquer）：遞歸地解決這些子問題。如果子問題的規模足夠小，可以直接求解。否則，繼續分解子問題，直到子問題可以直接求解。

3. 合并（Combine）：將子問題的解合并得到原問題的解。這個過程可能涉及到一些計算，但通常比直接解決原問題所需的計算量要少。

分治算法的優點：

1. 解決問題的原則是將大問題分解成小問題，降低了問題的復雜度。
2. 利用遞歸的方式解決問題，使得算法具有很好的可讀性和可維護性。
3. 通過合并子問題的解，可以避免重復計算，提高算法的效率。

分治算法的缺點：

1. 分治算法的效率往往受限于遞歸的深度和每層遞歸的開銷。在某些情況下，分治算法的效率可能不如其他算法。
2. 分治算法的遞歸調用可能導致棧空間的消耗較大，尤其是在遞歸深度較大的情況下。

分治算法在計算機科學中應用廣泛，例如：

1. 快速排序、歸并排序：這兩種排序算法都采用了分治策略，將待排序的序列分成兩部分，分別進行排序，然后將排序后的兩部分合并成一個有序序列。
2. 大整數乘法：分治算法可以用于加速大整數的乘法運算，例如Karatsuba算法。
3. 歐幾里得算法：用于求解兩個整數的最大公約數，采用分治策略，將較大數分解為若干個較小的數，然后遞歸地求解這些數的最大公約數，最后合并得到原問題的解。
4. 循環卷積：分治算法可以用于加速卷積運算，例如快速傅里葉變換（FFT）算法。

總之，分治算法是一種強大的解決問題的策略，通過將復雜問題分解成若干個較簡單的子問題，可以降低問題的復雜度，提高算法的效率。

下面本文將介紹幾種常見的分治算法應用。

歸并排序

【模板】排序

題目描述

將讀入的 $N$ 個數從小到大排序后輸出。

輸入格式

第一行為一個正整數 $N$。

第二行包含 $N$ 個空格隔開的正整數 $a_i$，為你需要進行排序的數。

輸出格式

將給定的 $N$ 個數從小到大輸出，數之間空格隔開，行末換行且無空格。

樣例 #1

樣例輸入 #1

5
4 2 4 5 1

樣例輸出 #1

1 2 4 4 5

提示

對于 $20\%$ 的數據，有 $1\le N\le 10^3$；

對于 $100\%$ 的數據，有 $1\le N\le 10^5$，$1\le a_i\le 10^9$。

分治算法（Divide and Conquer）

分治算法是一種算法設計范式，它通過將問題分解成多個小問題來解決，然后遞歸地解決這些小問題，最后將這些小問題的解合并起來得到原問題的解。分治算法通常包括三個步驟：

1. 分解（Divide）：將原問題分解成若干個規模較小但形式相同的子問題。
2. 解決（Conquer）：遞歸地解決這些子問題。如果子問題的規模足夠小，則直接解決。
3. 合并（Combine）：將子問題的解合并，以形成原問題的解。

歸并排序的分治策略

歸并排序是分治算法的一個經典例子。以下是歸并排序的分治過程：

1. 分解：將數組分成兩半。這是通過找到數組的中間位置來實現的。

2. 解決：遞歸地對這兩半進行歸并排序。這個過程會一直遞歸進行，直到每個子數組只有一個元素，這時子數組自然就是有序的。

3. 合并：將排序好的兩半合并成一個有序的數組。這是通過比較兩個子數組的前端元素，并將較小的元素放入結果數組中，直到所有元素都被合并。

圖解歸并排序

根據圖片，我們可以看到歸并排序的遞歸分解過程：

• 最初的數組是 ( [8, 4, 5, 7, 1, 3, 6, 1, 2] )。
• 歸并排序首先將數組分解為兩半：( [8, 4, 5] ) 和 ( [7, 1, 3, 6, 1, 2] )。
• 然后，每一半再次分解，直到每個子數組只有一個元素。
• 接著，遞歸地合并這些子數組，直到最終得到一個完全排序的數組。

時間復雜度

歸并排序的時間復雜度是 ( O(n \log n) )，其中 ( n ) 是數組的長度。這是因為：

• 分解：分解一個大小為 ( n ) 的數組需要 ( O(\log n) ) 層。
• 合并：每一層的合并操作需要 ( O(n) ) 的時間，因為需要遍歷整個數組來合并兩個子數組。
• 因此，總的時間復雜度是每層的 ( O(n) ) 乘以層數 ( O(\log n) )，得到 ( O(n \log n) )。

代碼如下所示：

#include<bits/stdc++.h>
using namespace std;
int merged[10000],n,a[10001];void merge(int l1,int r1,int l2,int r2){int i = l1,j = l2,cnt = 0;while(i <= r1 && j <= r2){if(a[i] < a[j]){merged[cnt++] = a[i++];}else{merged[cnt++] = a[j++];}}while(i <= r1){merged[cnt++] = a[i++];}while(j <= r2){merged[cnt++] = a[j++];}for(int t = 0;t < cnt;t ++) a[l1 + t] = merged[t];
}void merge_sort(int l,int r){if(l < r){int mid = (l+r)/2;merge_sort(l,mid);merge_sort(mid+1,r);merge(l,mid,mid+1,r);}
}int main(){cin >> n;for(int i = 0;i < n;i ++) cin >> a[i];merge_sort(0,n-1);for(int i = 0;i < n;i ++){cout << a[i];if(i != n-1) cout << " ";}
}

最大子段和

題目描述

給出一個長度為 $n$ 的序列 $a$，選出其中連續且非空的一段使得這段和最大。

輸入格式

第一行是一個整數，表示序列的長度 $n$。

第二行有 $n$ 個整數，第 $i$ 個整數表示序列的第 $i$ 個數字 $a_i$。

輸出格式

輸出一行一個整數表示答案。

樣例 #1

樣例輸入 #1

7
2 -4 3 -1 2 -4 3

樣例輸出 #1

4

提示

樣例 1 解釋

選取 $[3,5]$ 子段 { 3 , ? 1 , 2 } \{3, -1, 2\} {3,?1,2}，其和為 $4$。

數據規模與約定

• 對于 $40\%$ 的數據，保證 $n\le 2\times 10^3$。
• 對于 $100\%$ 的數據，保證 $1\le n\le 2\times 10^5$，$?10^4\le a_i\le 10^4$。

題解

分治法的思路是這樣的，其實也是分類討論。

連續子序列的最大和主要由這三部分子區間里元素的最大和得到：

• 第 1 部分：子區間 [left, mid]；
• 第 2 部分：子區間 [mid + 1, right]；
• 第 3 部分：包含子區間 [mid , mid + 1] 的子區間，即 [mid] 與 [mid + 1] 一定會被選取。
  對這三個部分求最大值即可。

說明：考慮第 3 部分跨越兩個區間的連續子數組的時候，由于 [mid] 與 [mid + 1] 一定會被選取，可以從中間向兩邊擴散，擴散到底 選出最大值。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
int a[N];int  crossMid(int low,int mid,int high){int leftSum = INT32_MIN,sum = 0;for(int i = mid;i >= low;i --){sum += a[i];if(sum > leftSum) leftSum = sum;}int rightSum = INT32_MIN;sum = 0;for(int i = mid+1;i <= high;i ++){sum += a[i];if(sum > rightSum) rightSum = sum;}return leftSum+rightSum;
}int maxSubArray(int low,int high){if(low == high) return a[low];int mid = (low+high)/2;int leftSum = maxSubArray(low,mid);int rightSum = maxSubArray(mid+1,high);int midSum = crossMid(low,mid,high);int tmp = max(leftSum,rightSum);return max(tmp,midSum);
}int main(){int n;cin >> n;for(int i = 0;i < n;i ++) cin >> a[i];cout << maxSubArray(0,n-1);return 0;
}

LCR 170. 交易逆序對的總數

在股票交易中，如果前一天的股價高于后一天的股價，則可以認為存在一個「交易逆序對」。請設計一個程序，輸入一段時間內的股票交易記錄 record，返回其中存在的「交易逆序對」總數。

示例 1:

輸入：record = [9, 7, 5, 4, 6]

輸出：8

解釋：交易中的逆序對為 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

限制：

0 <= record.length <= 50000

同類問題：

逆序對

題目描述

貓貓 TOM 和小老鼠 JERRY 最近又較量上了，但是畢竟都是成年人，他們已經不喜歡再玩那種你追我趕的游戲，現在他們喜歡玩統計。

最近，TOM 老貓查閱到一個人類稱之為“逆序對”的東西，這東西是這樣定義的：對于給定的一段正整數序列，逆序對就是序列中 $a_i>a_j$ 且 $i<j$ 的有序對。知道這概念后，他們就比賽誰先算出給定的一段正整數序列中逆序對的數目。注意序列中可能有重復數字。

Update:數據已加強。

輸入格式

第一行，一個數 $n$，表示序列中有 $n$個數。

第二行 $n$ 個數，表示給定的序列。序列中每個數字不超過 $10^9$。

輸出格式

輸出序列中逆序對的數目。

樣例 #1

樣例輸入 #1

6
5 4 2 6 3 1

樣例輸出 #1

11

提示

對于 $25\%$ 的數據，$n\le 2500$

對于 $50\%$ 的數據，$n\le 4\times 10^4$。

對于所有數據，$n\le 5\times 10^5$

請使用較快的輸入輸出

應該不會 $O(n^2)$ 過 50 萬吧 by chen_zhe

題解

逆序對統計：

1. 終止條件：當 ( l >=r ) 時，代表子數組長度為 1，此時終止劃分。
2. 遞歸劃分：計算數組中點 ( m )，遞歸劃分左子數組 reverseCount(l, m) 和右子數組 reverseCount(m + 1, r)。
3. 合并與逆序對統計：
   a. 暫存數組 a 閉區間 ([l, r]) 內的元素至輔助數組 tmp；
   b. 循環合并：設置雙指針 i，j 分別指向左/右子數組的首元素；
   • 當 ( i = m + 1 ) 時：代表左子數組已合并完，因此添加右子數組當前元素 tmp[j]，并執行 ( j = j + 1 )；
   • 否則，當 ( j = r + 1 ) 時：代表右子數組已合并完，因此添加左子數組當前元素 tmp[i]，并執行 ( i = i + 1 )；
   • 否則，當 tmp[i] ≤ tmp[j] 時：添加左子數組當前元素 tmp[i]，并執行 ( i = i + 1 )；
   • 否則（即 tmp[i] > tmp[j]）時：添加右子數組當前元素 tmp[j] 并執行 ( j = j + 1 )；此時構成 ( m - i + 1 ) 個「逆序對」，統計添加至 res。
4. 返回值：返回直至目前的逆序對總數 res。

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 5010000;
int n, a[MAXN], tmp[MAXN];long long reverseCount(int l, int r) {if (l >= r) return 0;int m = (l + r) / 2;long long res = reverseCount(l, m) + reverseCount(m + 1, r);int i = l, j = m + 1;for (int k = l; k <= r; k++) tmp[k] = a[k];for (int k = l; k <= r; k++) {if (i > m) { // 左子數組已完全復制a[k] = tmp[j++];} else if (j > r || tmp[i] <= tmp[j]) {a[k] = tmp[i++];} else {a[k] = tmp[j++];res += (m - i + 1); // 計算逆序對數量}}return res;
}int main() {cin >> n;for (int i = 0; i < n; i++) cin >> a[i];printf("%lld\n", reverseCount(0, n - 1));return 0;
}

進階問題

2884. 逆序對

暑假到了，小可可和伙伴們來到海邊度假，距離海灘不遠的地方有個小島，叫做歡樂島，整個島是一個大游樂園，里面有很多很好玩的益智游戲。

碰巧島上正在舉行“解謎題贏取免費門票”的活動，只要猜出來迷題，那么小可可和他的朋友就能在歡樂島上免費游玩兩天。

迷題是這樣的:給出一串全部是正整數的數字，這些正整數都在一個范圍內選取，誰能最快求出這串數字中“逆序對”的個數，那么大獎就是他的啦！

當然、主辦方不可能就這么簡單的讓迷題被解開，數字串都是被處理過的，一部分數字被故意隱藏起來，這些數字均用 ?1
來代替，想要獲得大獎就必須求出被處理的數字串中最少能有多少個逆序對。

小可可很想獲得免費游玩游樂園的機會，你能幫助他嗎？

注:“逆序對”就是如果有兩個數 A 和 B，A 在 B 左邊且 A 大于 B，我們就稱這兩個數為一個“逆序對”。

例如: 4 2 1 3 3 里面包含了 5 個逆序對:(4,2)、(4,1)、(4,3)、(4,3)、(2,1)。

假設這串數字由 5 個正整數組成，其中任一數字 N 均在 1～4 之間，數字串中一部分數字被 ?1 替代后，如:4 2 -1 -1 3，那么這串數字，可能是 4 2 1 3 3，也可能是 4 2 4 4 3，也可能是別的樣子。

你要做的就是根據已知的數字，推斷出這串數字里最少能有多少個逆序對。

輸入格式

第一行兩個正整數 N 和 K。

第二行 N 個整數，每個都是 ?1 或是一個在 1～K之間的數。

輸出格式

一個正整數，即這些數字里最少的逆序對個數。

數據范圍

1≤N≤10000
,
1≤K≤100

輸入樣例：

5 4
4 2 -1 -1 3

輸出樣例：

4

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int dp[N][110],n,a[N],ans,k;
int t1[110],t2[110],cnt;
void add(int tr[],int x,int c){for(int i=x;i<=k;i+=i&-i)tr[i]+=c;
}
int sum(int tr[],int x){int ans=0;for(int i=x;i;i-=i&-i)ans+=tr[i];return ans;
}
signed main(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]!=-1)add(t1,a[i],1);}for(int i=n;i>=1;i--){if(a[i]!=-1){ans+=sum(t2,a[i]-1);add(t2,a[i],1);add(t1,a[i],-1);}else{cnt++;for(int j=1;j<=k;j++)dp[cnt][j]=dp[cnt-1][j]+sum(t2,j-1)+sum(t1,k)-sum(t1,j);dp[cnt][k+1]=1e9;for(int j=k;j>=1;j--)dp[cnt][j]=min(dp[cnt][j],dp[cnt][j+1]);}}int mi=1e9;for(int i=1;i<=k;i++)mi=min(mi,dp[cnt][i]);cout<<ans+mi;
}