---

文章目錄

• 快速排序
• 歸并排序
• 二分
  • 整數(shù)二分
  • 浮點數(shù)二分
• 高精度????????
  • 高精度加法
  • 高精度減法
  • 高精度乘法
  • 高精度除法
• 前綴和
  • 一維前綴和
  • 二維前綴和
• 差分
  • 一維差分
  • 二維差分
• 雙指針
• 位運算
• 離散化
• 區(qū)間合并

---

一、快速排序

思想：1.首先確定一個分界點（隨機取任意一點為分界點，一般取中點）

?????????? 2.將小于x的數(shù)移動到左邊，大于x的數(shù)移動到右邊，將區(qū)間分為[l,j],[j+1,r];

?????????? 3.遞歸左右兩個區(qū)間即可。

void quick_sort(int q[], int l, int r)
{if (l >= r) return;int i = l - 1, j = r + 1, x = q[l + r >> 1];while (i < j){do i ++ ; while (q[i] < x);do j -- ; while (q[j] > x);if (i < j) swap(q[i], q[j]);}quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

二、歸并排序

思想：1.首先去數(shù)組的中間數(shù)作為分界點.

?????????? 2.遞歸分界點的左右兩個區(qū)間

?????? ? ? 3.將左右兩邊進行合并。

int tmp[N];void Merge_sort(int a[], int l, int r)
{if (l >= r) return;int mid = (l + r) >> 1;//先分后合Merge_sort(a, l, mid);Merge_sort(a, mid + 1, r);int i = l, j = mid + 1, k = 0;//歸并while (i <= mid && j <= r){if (a[i] <= a[j]) tmp[k++] = a[i++];else tmp[k++] = a[j++];}//續(xù)尾while (i <= mid) tmp[k++] = a[i++];while (j <= r) tmp[k++] = a[j++];for (i = l, j = 0; i <= r;)a[i++] = tmp[j++];
}

三、二分

思想：可以劃分為滿足某種性質(zhì)與不滿足某種性質(zhì)的兩個區(qū)間。

1.整數(shù)二分

bool check(int x) {/* ... */} // 檢查x是否滿足某種性質(zhì)// 區(qū)間[l, r]被劃分成[l, mid]和[mid + 1, r]時使用：
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;    // check()判斷mid是否滿足性質(zhì)else l = mid + 1;}return l;
}
// 區(qū)間[l, r]被劃分成[l, mid - 1]和[mid, r]時使用：
int bsearch_2(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}return l;
}

2.浮點數(shù)二分

bool check(double x) {/* ... */} // 檢查x是否滿足某種性質(zhì)double bsearch_3(double l, double r)
{const double eps = 1e-6;   // eps 表示精度，取決于題目對精度的要求while (r - l > eps){double mid = (l + r) / 2;if (check(mid)) r = mid;else l = mid;}return l;
}

四、高精度

1.高精度加法

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{if (A.size() < B.size()) return add(B, A);vector<int> C;int t = 0;for (int i = 0; i < A.size(); i ++ ){t += A[i];if (i < B.size()) t += B[i];C.push_back(t % 10);t /= 10;}if (t) C.push_back(t);return C;
}

2.高精度減法

// C = A - B, 滿足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{vector<int> C;for (int i = 0, t = 0; i < A.size(); i ++ ){t = A[i] - t;if (i < B.size()) t -= B[i];C.push_back((t + 10) % 10);if (t < 0) t = 1;else t = 0;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}

3.高精度乘法

// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{vector<int> C;int t = 0;for (int i = 0; i < A.size() || t; i ++ ){if (i < A.size()) t += A[i] * b;C.push_back(t % 10);t /= 10;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}

4.高精度除法

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{vector<int> C;r = 0;for (int i = A.size() - 1; i >= 0; i -- ){r = r * 10 + A[i];C.push_back(r / b);r %= b;}reverse(C.begin(), C.end());while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}

五、前綴和

1.一維前綴和

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

#include<iostream>using namespace std;const int N = 100010;int n, m;
int a[N], s[N];int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> n >> m;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++)s[i] = s[i - 1] + a[i];while (m--){int l, r;cin >> l >> r;cout << s[r] - s[l - 1] << endl;}return 0;
}

?2.二維前綴和

?S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

#include<iostream>using namespace std;const int N = 1010;int n, m, q;
int a[N][N], s[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> n >> m >> q;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> a[i][j];for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];while (q--) {int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]<<endl;}return 0;
}

六、差分

差分數(shù)組的定義：記錄當(dāng)前位置的數(shù)與上一位置的數(shù)的差值.

?差分的作用：在差分數(shù)組的 減去 在位置處加上,就能達到整個區(qū)間修改的操作.

1. 快速處理區(qū)間加減操作：
2. 詢問區(qū)間和:處理查詢.
3. 求出前綴和.

1.一維差分

給區(qū)間[l, r]中的每個數(shù)加上c：B[l] += c, B[r + 1] -= c

#include<iostream>using namespace std;const int N = 100010;int n, m;
int a[N], b[N];void insert(int l, int r, int c)
{b[l] += c;b[r + 1] -= c;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> n >> m;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++)insert(i, i, a[i]);while (m--) {int l, r, c;cin >> l >> r >> c;insert(l, r, c);}for (int i = 1; i <= n; i++)b[i] += b[i - 1];for (int i = 1; i <= n; i++)cout << b[i] << " ";return 0;
}

2.二維差分

給以(x1, y1)為左上角，(x2, y2)為右下角的子矩陣中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

#include<iostream>using namespace std;const int N = 1010;int n, m,q;
int a[N][N], b[N][N];void insert(int x1, int y1, int x2, int y2,int c)
{b[x1][y1] += c;b[x2 + 1][y1] -= c;b[x1][y2 + 1] -= c;b[x2 + 1][y2 + 1] += c;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> n >> m>>q;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> a[i][j];for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)insert(i, j, i, j, a[i][j]);while (q--) {int x1, y1, x2, y2, c;cin >> x1 >> y1 >> x2 >> y2 >> c;insert(x1, y1, x2, y2, c);}for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cout << b[i][j] << " ";return 0;
}

七、雙指針

在區(qū)間問題上，暴力的做法的復(fù)雜度往往達到O(n^2）復(fù)雜度，而雙指針的思想挖掘區(qū)間“單調(diào)”性質(zhì)將復(fù)雜度降到O(n)。

常見問題分類：
??? (1) 對于一個序列，用兩個指針維護一段區(qū)間
??? (2) 對于兩個序列，維護某種次序，比如歸并排序中合并兩個有序序列的操作

for (int i = 0, j = 0; i < n; i ++ )
{while (j < i && check(i, j)) j ++ ;// 具體問題的邏輯
}

八、位運算

求n的第k位數(shù)字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

常用技巧：

1、?用于整數(shù)的奇偶性判斷（n&1）

2、?判斷n是否是2的正整數(shù)冪（(!(n&(n-1)) )&& n）

3、?統(tǒng)計n中1的個數(shù)

九、離散化

思想：1.首先操作設(shè)計的下標(biāo)，把將要存數(shù)字的下標(biāo)與求和范圍兩端的下標(biāo)，存入小數(shù)組q中。

????????2.將小數(shù)組q進行排序。

????????3.創(chuàng)建出一個與小數(shù)組q相同大小的數(shù)組s，從數(shù)組q中找出對應(yīng)大數(shù)組要存入數(shù)據(jù)的位置的映射，在s相同位置存入數(shù)據(jù)（可以利用二分的思想）。

????????4.找大數(shù)組求和范圍兩端點在q中的映射位置，在數(shù)組s對應(yīng)映射位置求和即可，可用前綴和。

vector<int> alls; // 存儲所有待離散化的值
sort(alls.begin(), alls.end()); // 將所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重復(fù)元素// 二分求出x對應(yīng)的離散化的值
int find(int x) // 找到第一個大于等于x的位置
{int l = 0, r = alls.size() - 1;while (l < r){int mid = l + r >> 1;if (alls[mid] >= x) r = mid;else l = mid + 1;}return r + 1; // 映射到1, 2, ...n
}

十、區(qū)間合并

思想：1.首先我們以每個分區(qū)的左側(cè)為標(biāo)準(zhǔn)進行排序，這樣我們的每次區(qū)間合并只需要采用當(dāng)前區(qū)間和下一個區(qū)間對比即可，此外我們的左側(cè)不需要改變。

????????2.右側(cè)的情況分為三種：包裹,接觸，不接觸 分別對應(yīng)著右側(cè)邊界為a.r,b.r以及兩個區(qū)間都添加的情況。

思路：1.按區(qū)間的左端點排序。

????????2.從左到右掃描，維護一個當(dāng)前區(qū)間

????????3.每次遍歷的區(qū)間和當(dāng)前區(qū)間有三種情況：

????????（1）右端點小于當(dāng)前區(qū)間的左端點，當(dāng)前區(qū)間不變。

????????（2）右端點大于當(dāng)前區(qū)間的右端點，當(dāng)前區(qū)間變長。

??????? （3）左端點大于當(dāng)前區(qū)間右端點，將區(qū)間置為當(dāng)前區(qū)間。

// 將所有存在交集的區(qū)間合并
void merge(vector<PII> &segs)
{vector<PII> res;sort(segs.begin(), segs.end());int st = -2e9, ed = -2e9;for (auto seg : segs)if (ed < seg.first){if (st != -2e9) res.push_back({st, ed});st = seg.first, ed = seg.second;}else ed = max(ed, seg.second);if (st != -2e9) res.push_back({st, ed});segs = res;
}