cpp 模板

最后更新于：2022年6月25日 下午

编写编译器易优化、易读、易拓展、自解释的代码，并且配套文档。

C++ 模板的 代码，文档，比赛源码 都已放在 github 上

博弈，多项式, 图论，字符串, C++ 学习笔记 单独成篇

C++11 是基本，C++14 是福报，C++17 是奢望，C++2x 在梦里，只能用 C++98 那赶紧跑路

我对 C++ 的感情，犹如对祖国一样充满希望。它自然有很多被诟病的地方，但不影响它在不断完善

代码风格一直在变化，存于心中

通用技巧

递归程序防止爆栈

  • 在 Windows 上，通常的方法是在 编译选项 中加入 -Wl,--stack=1000000000
  • 在 Linux 上，通常的方法是在运行程序前 在终端内 执行 ulimit -s unlimited （WSL1 下无法设置可惜）

C++ 黑魔法：\(n^2\) 过百万，编译器优化+指令集优化

博文 和 ppt

但是实际上不需要这么麻烦，仅需在头部添加下面代码（codeforces 上支持）

1
2
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,abm,mmx,avx,avx2,popcnt,tune=native")

示例：

bitset 高端压位卡常

典型应用，求传递闭包，高维偏序。bitset 还有两个好用的 builtin 函数: _Find_first, _Find_next

概率问题永不 TLE 的技巧

1
2
3
4
5
// 概率问题永不 TLE 的技巧
auto begin = std::chrono::steady_clock::now();
while ((std::chrono::steady_clock::now() - begin).count() < 5e8) { // 数值取时限的一半
  // do something
}

Python 输入样例（以备不时之需，用 PyPy3 提交）

用 Python 过的一次大数题：490C

1
2
3
4
5
6
7
8
9
# 多 case 输入
for _ in range(int(input())):
# 单行输入
    n = int(input())
# 两个元素一行输入
  a, b = map(int, input().split())

# 提前结束
exit()

取平均值（防溢出，C++20 就有 mid 函数了）

1
2
(x & y) + ((x ^ y) >> 1) // 向下取整
(x | y) - ((x ^ y) >> 1) // 向上取整

交互式题目模板

gym101021: Guess the Number 需要 fflush(stdout);（对于 scanf/printf） 或 std:::cout << std::flush （对于 std::cin/std::cout） 来刷新缓冲区，不过 std::endl 会自动刷新一次缓冲区，所以此时可以省略。

注意 std::endl 和 \n 的区别是前一个刷新缓冲区，后一个不刷新。仅在交互问题或者 debug 的时候使用 std::endl;

负数下标技巧

1
2
3
const int N = 1e5 + 2;
int aa[N];
int *a = (aa + N / 2);

可用于 \(O(1)\) 首尾插入或删除元素，访问第 \(i\) 个元素。 当然也可以用 std::deque 加一个标号，实现上述操作

优雅的输出技巧

1
2
3
4
int n = 10;
for(int i = 0; i < n; ++i) {
  std::cout << i << " \n"[i == n - 1];
}

带取整的函数取最值的技巧

  • 先考虑不取整的情况，然后一般这个值是可能的最小值或者最大值
  • 然后通过循环看是否满足取整的情况

输出全排列

1
2
3
4
5
6
7
8
9
10
void permutation(int n){
  std::vector<int> x(n);
  std::iota(x.begin(), x.end(), 1);
  do {
    std::for_each(x.begin(), x.end(),[](int i){
      std::cout << i;
    });
    std::cout << std::endl;
  } while (std::next_permutation(x.begin(), x.end()));
}

输出全排列的原理

首先初始状态从小到大排列，然后对每一个状态考虑它的后缀，如果后缀是从大到小排列，再考虑向前一位的后缀，直到不是从大到小排列，然后找比第一个位置大的最小值放在开头，其它位置排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import math
def permutation(n):
  ans = []
  cnt = math.factorial(n);
  r = list(range(1, n + 1))
  ans.append(r.copy())
  cnt -= 1
  while cnt > 0:
    i = n - 1
    while r[i - 1] > r[i]: i -= 1
    r[i:] = r[i:][::-1]
    j = i
    while r[j] < r[i - 1]: j += 1
    r[i - 1], r[j] = r[j], r[i - 1]
    ans.append(r.copy())
    cnt -= 1
  return ans

for i in range(1,5):
  print(permutation(i))

通用知识

产生 log 的几个原因

  1. 二分，三分
  2. \(1 + \frac{1}{2} + \cdots \frac{1}{n} \sim \log n\)
  3. \(\frac{1}{2} + \cdots \frac{1}{p} \sim \log \log n\)
  4. 树状数组，线段树
  5. 堆排序
  6. 分治
  7. FFT、FWT
  8. 重链剖分
  9. 倍增（太好用了，特别是 nxt 数组进行加速）

产生根号的几个原因

  1. 朴素判断素数
  2. 整除分块：\(\lfloor \frac{n}{i} \rfloor\) 的值域是 \(O(\sqrt{n})\) 的
  3. \(\max(x + \frac{n}{x})\)
  4. 网络流中 HLPP（没读过这篇复杂度分析的论文，不懂）
  5. 分块处理，分块打表
  6. 莫队（离线算法）

\(O(1)\) 额外空间复杂度算法

大小步(Baby step gain step)

复制链表

二叉树遍历 Morris 算法

const VS constexpr

从 2021-4-27 开始使用 constexpr。对于变量而言，它们的本质区别，一个编译器初始化，一个运行时初始化。

int VS long long

以前当 int 类型出现带模乘法的时候，我们一般就直接使用 LL 了，不用强制类型转化了。但是后来转而使用 int 了。

注意到 LL(a) * b % n 和 1LL * a * b 在汇编意义下没有区别。两种情况哪个方便写那个。放弃 LL 的主要理由：

  • 本身就是 int 型的变量，为什么用 LL 存储呢？
  • 内存减少一半
  • 在 32 位机器上更快。

最大最小值分配律

\[ \begin{aligned} \min(\max(x, a), b) = \max(\min(x, b), \min(a, b)) \\ \max(\min(x, a), b) = \min(\max(x, b), \max(a, b)) \end{aligned} \]

例题：Atcoder abc196E

cout, cerr, clog 的区别

cerr 可看作自动刷新缓冲区的 clog。 cout 和 clog 的区别就是 clog 直接打印在屏幕上，而我们文件输入输出的时候使用 freopen("out", "w", stdout) 后 cout 会输出到 out 文件中，而 clog 依然打印在屏幕中，这就很有用了。

动态规划思想

动态规划的能力犹如程序员的内功

水涨船高技巧

把一个集合中所有元素加一个常数，可以不操作，加在水位线上即可

Meet in Middle(拆半搜索法)

类似于动态规划，是一种思想。特别适合处理指数复杂度。

例题：AtCoder abc184F，当然针对此题可以深搜剪枝法。

Small to large（把小的合并到大的里面去）

例子：并查集（dus），map 的合并，树上启发式合并（dus on tree)，重链剖分。

例题：600E 的 题解

倍增思想（太强了）

例子：RMQ，LCA。nxt 数组进行加速

大小端

  • C++20 std::endian
  • 用一个 Union（一个 uint32 的数和一个 长为 4 的 uint8 的数组
  • 用一个 char* 指向一个 int 型的数，然后取指针的值
  • python -c "import sys; print(sys.byteorder)"

ABI 兼容问题

整除：C++ VS Python

  • C/C++ 中，整数除法 / 是向 0 取整(int(x)也是向 0 取整)
  • Python/Sagemath 中，整数除法 // 是向下取整。

在 C++ 中一定不要用 (x - 1) / n + 1 的姿势向上取整！

位运算

位运算的关系

  • 异或 1 改变，异或 0 不变
  • \(a \oplus b\) 在某位为 0，表示在此位它们相等，反之不等。
  • \(a \oplus b = (a \mid b) \oplus (a \And b)\)
  • \(a \oplus b = (a \mid b) - (a \And b)\)
  • \(a + b = (a \mid b) + (a \And b)\)
  • \(a + b = (a \oplus b) + 2 (a \And b)\)
  • (a & b) | c = (a | b) & (a | c)
  • (a | b) & c = (a & b) | (a & c)
  • (a | b) ^ 1 = (a ^ 1) & (b ^ 1)
  • (a & b) ^ 1 = (a ^ 1) | (b ^ 1)
  • (a | b) ^ c 和 (a & b) ^ c 可以逐位转化，因此任何一个数 x 经过任意多次的&, |, ^ 运算最终都可以写成 ((x ^ a) & b) | c。

最高位后面位取反 \(O(1)\)

1
2
3
int reverseBit(int n) {
  return n ^ ((1 << 32 - __builtin_clz(n)) - 1);
}

最低位 1 置 0: x = x & (x - 1)

树状数组中使用的 lowbit(x) = x & (-x) 得到 x 的最大 2 的幂次因子

mask 位上暴力枚举

1
2
3
for (int i = n; i; i = (i - 1) & n) {
  // do something
}

Gosper's Hack：n 个集合中选 k 个

思路：想想怎么把 1011100 变成 110011

1
2
3
4
5
6
7
8
9
10
11
void GospersHack(int n, int k) {
  int cur = (1 << k) - 1;
  int limit = (1 << n);
  std::vector<int> r;
  while (cur < limit) {
    // do something
    int lb = cur & -cur;
    int r = cur + lb;
    cur = (((r ^ cur) >> 2) / lb) | r;
  }
}

异或运算是一种很神奇用途很广的运算. 从性质上, 异或运算作为二元运算, 关于所有非负整数构成一个 Abel 群, 0 作为幺元, 每个元的逆元都是自身(等价于说 \(char(N ^ \star,xor)=2\))。

异或找出唯一出现奇数次的数

把这一堆数全体直接异或即可.

这个方法可以推广到找出两个只出现奇数次的, 其它出现偶数次的两个数, 方法就是先异或之后的值按照最高位进行标记然后分成两组, 再来一遍

数学

常用组合数公式及其直观解释

对任意实数，定义：\(\binom{\alpha}{k} = \frac{\alpha(\alpha - 1) \cdots (\alpha - k + 1)}{k !}\) 所以我们有：

\[ \binom{-n}{k} = (-1)^{k} \binom{n + k - 1}{k} \]

\[ \binom{n + 1}{k + 1} = \binom{n}{k} + \binom{n}{k + 1} \] > 最后一个数，先还是不选，这是一个问题

\[ {n \choose k}{k \choose i}  = {n \choose i} {n - i \choose k - i} \]

 组合意义理解：\(n\) 个人中选出 \(i\) 个一流人才， \(k - i\) 个二流人才

\[{n + m \choose k} = \sum_{i + j = k} {n \choose i} {m \choose j}\]

组合意义理解：\(n, m\) 两个堆选出 \(k\) 个人

拓展 Euler 定理

数论中欧拉定义说：若 \(\gcd(a, m) = 1\) 则 \(a^{\phi(m)} \equiv 1 \mod m\)。

类似于拓展的 Fermat 小定理：\(a^p \equiv a \mod p\)，我们有拓展 Euler 定理：

\[ a^n \equiv a^{n \mod \phi(m) + phi(m)} \mod m \]

证明对 \(m\) 素因子分解，再利用 Euler 函数是可乘函数，显然。

求原根

首先，模 \(m\) 有原根的充要条件是：\(m=2,4,p^a,2p^a\)，其中 \(p\) 为奇素数。

对于求模奇素数 \(p\) 的原根方法：对 \(p-1\) 素因子分解：\(p-1 = p_1^{a_1} \cdots p_s^{a_s}\) 若恒有 \[ g^{\frac{p-1}{p_i}} \neq 1(\mod \; p) \] 则 \(g\) 是 模 \(p\) 的原根。对于 \(p^a\) 的原根 为 \(g\) 或 \(g + p\)，若 \(p^a\) 的原根为 \(g_a\) 而 \(2p^a\) 的原根为 \(g_a\) 和 \(g_a + p^a\) 的中奇数者。所有原根：可以先求出一个原根，然后所有的数便是 \(g^0, g^1, \cdots, g^{\phi(m) - 1}\), 所有原根就是那些 \(\gcd(i, \phi(m)) = 1\) 的 \(g^i\) (证明见 P150《数论基础》潘承洞)。

基于上述方法的代码实现

另外更好的做法：

我们首先求出 \(m = \phi(n)\)，然后一个个的搜，搜索的时候附带把很多点都给剔除了，所以很快就能找到！具体代码

自然数方幂和精确版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <boost/multiprecision/cpp_int.hpp>
using BINT = boost::multiprecision::cpp_int;

BINT f[N];
BINT getPowSum(LL n, int k) { // k<1000
  if (k == 0) return BINT(n);
  if (p[1] != 2) spf();
  int nk = 2 * k + 1;
  f[0] = 0;
  f[1] = 1;
  auto bPow = [](BINT x, int n) -> BINT {
    BINT r(1);
    for (; n; x *= x, n >>= 1) if (n&1) r *= x;
    return r;
  };
  for (int i = 2; i <= nk + 1; ++i) {
    if (sp[i] == i) f[i] = bPow(BINT(i), k);
    else f[i] = f[sp[i]] * f[i / sp[i]];
  }
  for (int i = 1; i <= nk; ++i) f[i] += f[i - 1];
  if (n <= nk) return f[n];
  BINT res = 0, tl = 1, tr = 1;
  for (int i = nk - 1; i >= 0; --i) tr = tr * (n - i - 1) / (nk - i);
  for (int i = 0; i <= nk; ++i) {
    if ((nk - i) & 1) res -= f[i] * tl * tr;
    else res += f[i] * tl * tr;
    tl = tl * (n - i) / (i + 1);
    tr = tr * (nk - i) / (n - i - 1);
  }
  return res;
}

需要下载boost 包 类似的包还有 NTL，GMP

生成函数

Polya 说过：生成函数就像袋子，把一个个零碎的小部件放在一个袋子里，就可以优雅高效的只关注袋子了。

在 codeforces 上 zscoder 大佬给了一个 入门教程 和 进阶教程 还有 MiFaFaOvO 的 终极教程

生成函数分两种：Original generating function，Expentional generating function，选择哪一种是看问题中是否牵扯组合数。无论哪一种都能保存原数列的全部信息，并且由于级数可以使用微积分和常微分方程的技术，所以会变得更好处理。然后大概率可以优化算法复杂度 \(O(n^2) \to O(n \log n)\)

关于生成函数多项式的处理：https://cp-algorithms.com/algebra/polynomial.html

多项式高效运算模板：https://github.com/e-maxx-eng/e-maxx-eng-aux/blob/master/src/polynomial.cpp

生成函数一般的处理思路：计算生成函数，分解成有分母不超过二次的分式之和，然后每一个二次的分母部分找一个递推数列来搞定。

OI-wiki 多项式运算

多项式计数杂谈 很值得学习一下。

多项式取对数和指数

\(B(z) = e^{A(z)}\)，即 \(A(z) = \ln B(z)\) (不妨假设 \(A(0) = 0\) 或等价地 \(B(0) = 1\))

那么 \(B'(z) = A'(z) \cdot B(z)\), 所以 \([z^{n - 1}] B'(z) = \sum_{k = 0}^{n - 1} [z^k] A'(z) \cdot B(z) [z^{n - 1 - k}] = \sum_{k = 1}^{n} [z^{k - 1}] A'(z) \cdot B(z) [z^{n-k}]\)，从而 \[ n [z^n] B(z) = \sum_{k = 1}^n k [z^k] A(z) \cdot B(z) [z^{n - k}] \] 上式等价于 \[ n [z^n] A(z) = n [z^n] B(z) - \sum_{k = 1}^{n - 1} k [z^k] A(z) \cdot B(z) [z^{n - k}] \]

参考：Soulist

差分约束

\(n\) 个变量，\(m\) 个约束条件，每个约束条件都形如 \(x_i - x_j \leq c_k\)，此时我们从节点 j 向 i 连一条长度为 \(c_k\) 的有向边，（如果有等于号，我们就连两条），设 dist[0] = 0，然后 0 节点向所有节点连一条长度为 0 的有向边。跑单源最短路，如果环中有负环，那么无解，否则 \(x_i = dist[i]\) 为一组解。

可用图论中 Bellman-Ford 算法，或 spfa（随笔图跑的快），例题：LOJ P1993，spfa 做法，Bellman-Ford 做法

变式：\(\frac{x_i}{x_j} \leq c_k\)（取 log 即可）

数据结构

逆序数

  1. 直接求 \(O(n^2)\) 没啥好写的。
  2. 把原数组每个位置进行编号，排序，然后每次把最大的数的编号丢进树状数组中，丢进去先看这个编号前面有多少个数，累加一下就可以了，\(O(n^2)\)，结合下面树状数组的知识还是很简单的。
  3. 带离散化的树状数组（就是如果元素的数值特别大，树状数组内存就不够了，所以需要离散化一下）
  4. 归并的求（不会也不想搞 0.0）
  5. 逐位处理（代码如下）

树状数组加强版（区间更新，区间求和，编号从 1 开始）

有了单点更新的树状数组，只需简单利用差分就可以变成区间的更新了。 设原始数组为 a[1 ~ n]， 定义 c[i] = a[i] - a[i - 1], (a[0] = 0) 显然

\[ \sum_{i = 1}^m a_i = \sum_{i = 1}^m (m - i + 1) c_i = m \sum_{i = 1}^m c_i - \sum_{i = 1}^m (i - 1) c_i \]

比如对区间 [l, r] 做更新，那么就只需更新两点：r + 1, l ，套用之前的类就行了。

注意在树状数组中搜索本来应该是 \(O(\log ^2 n)\)，但是因为在 \(2^i\) 的位置搜索时，一步到位。所以复杂度会降到 \(O(\log n)\)：理论依据

线段树节点上界（不管是不是左闭右开）

首先显然总节点 \(m\) 上界为 \(4n\)，并且可以证明 \(\frac{m}{n}\) 的上确界为 \(4\)，下确界为 \(2\) 注意到如果 \(n = 2^k + 2^{j + 1}\) 时，则 \(m = 2 ^{k + 1} + 2^k + \cdots 2^{k - j} + 1\)，所以 \(\frac{m}{n} = \frac{4 - 2^{-j} + 2^{-k}}{1 + 2^{j + 1 - k}}\)，对任意 \(\epsilon > 0\) 存在 \(j\) 使得 \(4 - 2 ^{-j} > 4 - \epsilon\)， 然后让 \(k\) 趋于无穷，那么显然 \(\frac{m}{n}\) 上极限为 \(4\).（\(n = 40\) 时， \(\frac{m}{n} > 3\)，\(n = 2^{20} + 2^{10} = 1049600\) 时，\(\frac{m}{n} > 3.99\)）

根据 jiangly 的做法：这里必然会得到 \(m < 4 \cdot 2^{\log_2 n}\) 确实如此。这与上面的结论不矛盾，只是更加精确罢了

和与最大值的线段树模板（如果单纯求和，可以用树状数组），现在使用左闭右开线段树，且使用吉老师 pushTag 版本

三分法简单版

单峰函数可以这么做，以下为求上峰的版本

1
2
3
4
5
6
7
8
int l = 1, r = 1e9;
while (r > l) {
  int m = (r - l) / 3;
  int lm = l + m, rm = r - m;
  if (f(lm) < f(rm)) r = rm - 1;
  else l = lm + 1;
}
return l;

标准三分法用黄金分割的原因

我们不妨设原始区间为 [0, 1]，我们在其中选两个点 0 < a < b < 1，然后比较 f(a) 和 f(b)，然后再相应改变区间。然后重复上述过程。如果我们能充分利用计算过的值，也就是说假设更新后的区间为 [0, b] 那么我们自然想让 a 的计算值充分被利用，所以我们想再选的两个点的其中一个是 a，如果更新后区间为 [a, 1] 同理。也就是说我们有策略 \[ \frac{a}{b} = b, \frac{b - a}{1 - a} = a \] 化简可得 \(b(1 + b) = 1\)，即 \(b = \frac{\sqrt{5} - 1}{2}, a = b ^ 2 = \frac{3 - \sqrt{5}}{2} = 1 - b\)。 > 注意到上述 \(b\) 的值正好是黄金分割 0.618...

背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const int MAX = 1e5 + 5;
int r[MAX];
void pack(int cash, int num, int v, int w) {
  if (num == 0 || w == 0 || v == 0) return;
  if (num == 1) { //  0-1背包
    for (int i = cash; i >= v; --i)
      r[i] = max(r[i], r[i - v] + w);
    return;
  }
  if (num * v >= cash - v + 1) { //完全背包
    for (int i = v; i <= cash; ++i)
      r[i] = max(r[i], r[i - v] + w);
    return;
  }
  int q[MAX], s[MAX], head, tail;
  for (int j = 0; j < v; ++j) { //多重背包
    q[0] = r[j];
    s[0] = head = tail = 0;
    for (int i = 1, k = j + v; k <= cash; ++i, k += v) {
      q[i] = r[k] - i * w;
      while (s[head] < i - num) ++head;
      while (head <= tail && q[tail] < q[i]) --tail;
      s[++tail] = i;
      q[tail] = q[i];
      r[k] = q[head] + i * w;
    }
  }
}

堆与 STL 优先队列

可以使用 C++STL 的 priority_queue，查找可用 lower_bound 和 upper_bound。C++ STL 中优先队列是用堆来实现的。用途十分广泛，例如加速最小生成树，拓扑排序，等等。 堆的实现一般是用数组。 我们可以用 1 作为树的根， 对每一个节点 \(x\)， 它的两个节点分别就是 \(2x\) 和 \(2x + 1\) 平时都用 x << 1, x << 1 | 1 表示。 堆只支持三个操作:

  1. 插入一个节点(我们实现时是插入最尾部， 这样保证了是一个完全二叉树) \(O(\log n)\)
  2. 删除最大键值节点（删除根元素的值） \(O(\log n)\)
  3. 输出最大键值节点（查看根元素的值） \(O(1)\)

单调队列：解决滑动窗口问题（固定长度内的最值问题）

知乎 Pecco 讲的很好（建议直接去看它的讲解）： > 如果一个选手比你小还比你强，你就可以退役了。——单调队列的原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 求每个长度为 m 的区间最大值的编号
std::vector<int> monicDequeMax(std::vector<int> &a, int m) {
  std::vector<int> r;
  std::deque<int> Q;
  for (int i = 0; i < a.size(); ++i) {
    if (!Q.empty() && i - Q.front() >= m) Q.pop_front();
    // 如果求最小值，大于号改成小于号即可
    while (!Q.empty() && a[i] > a[Q.back()]) Q.pop_back();
    Q.push_back(i);
    // 如果需要返回值，就在下面加入 a[Q.front()]
    if (i >= m - 1) r.emplace_back(Q.front());
  }
  return r;
}

例题：LOJ P2216：这个是二维的，我们可以一维一维的处理

单调队列优化 DP

例题：LOJ P2034：取数字使得和最大，但是不能取连续 k 个数

肯定是 dp 问题，如果把 dp[i] 定义成取第 i 个，前 i 个结果的最值，会发现很搞。 因此我们反过来考虑。考虑删除若干个数，且删除的间隔不超过 k，求删除的最小和。最终答案就是总和减去最小和。设 dp[i] 表示删除 i，且满足性质的前 i 个数的答案。那么显然 \(dp[i] = a[i] i \leq k\)，\(dp[i] = a[i] + \min_{i - k \leq j \leq i - 1} dp[j]\)。注意最终答案不是总和减去 dp 的 最小值，而是 \(dp[n - k - 2, \cdots, n - 1]\) 的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;
int main() {
  // freopen("in", "r", stdin);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, k;
  std::cin >> n >> k;
  std::vector<int> a(n), dp(n);
  LL s = 0;
  for (auto &x : a) {
    std::cin >> x;
    s += x;
  }
  std::deque<int> Q;
  for (int i = 0; i < n; ++i) {
    dp[i] = a[i];
    if (i >= k + 1) dp[i] += dp[Q.front()];
    if (!Q.empty() && i - Q.front() >= k + 1) Q.pop_front();
    while (!Q.empty() && dp[i] <= dp[Q.back()]) Q.pop_back();
    Q.push_back(i);
  }
  std::cout << s - *std::min_element(dp.end() - k - 1, dp.end());
  return 0;
}

单调栈：形式更简单应用更广

知乎 Pecco 的精彩讲解：维护一个栈，当我们碰上一个新元素，我们知道，越靠近栈顶的元素离新元素位置越近。所以不断比较新元素与栈顶，如果新元素比栈顶大，则可断定新元素就是栈顶的下一个更大元素，于是弹出栈顶并继续比较。直到新元素不比栈顶大，再将新元素压入栈。显然，这样形成的栈是单调递减的。

应用一：求下一个比自身大的元素位置（下可以改成上，大可以改成小）

洛谷模板题：LOJ P5788

应用二：两个元素间所有元素均（不）大/小于这二者。

洛谷进阶题：LOJ P1823，问有多少对元素，它们之间没有比它们都大的元素。

单调栈优化 DP

应用一优化 DP 例题：1313C2，首先最优答案肯定时先递增后递减的。相当于有一个制高点，枚举制高点，自然有 \(O(n^2)\) 的算法。但是可以优化到 \(O(n)\)

应用二优化 DP 例题：1407D，每次跳跃，它们之间的元素都严格大于它们或者严格小于它们。首先设 dp[i] 为到达 i 最小跳跃数，那么显然 \(\displaystyle dp[i] = \min_{j \to i} dp[j] + 1\)。我们可以用两个单调栈来看那些 j 能跳到 i。

几何

分治法求平面最短距离（任何距离都适用）

首先根据横坐标排序，然后取中位数假设处理好了左右两边的值，然后合并中间的值，首先距离中心点的横坐标不能超过已知的最小值，然后把筛出来的点按照纵坐标排序，然后 \(O(n)\) 更新答案。总题复杂度 \(O(n \log^2 n)\)，如果使用归并排序理论复杂度为 \(O(n \log n)\)，但是实际效果并不如直接排序。

例题：[https://www.luogu.com.cn/problem/P1429] 和 LOJ P6247

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
using Point = std::pair<double, double>;
// 这里不要用 dist2，否则很多比较的地方都要平方，反而不优雅了。
double dist (const Point& p, const Point &q) {
  double x = q.first - p.first, y = q.second - p.second;
  return std::sqrt(x * x + y * y);
};
double minDist(std::vector<Point> a) {
  double d = DBL_MAX;
  int n = a.size();
  if (n <= 1) return d;
  std::sort(a.begin(), a.end());
  std::function<void(int, int)> merge = [&](int l, int r) {
    if (r - l <= 1) return;
    if (r - l == 2) {
      d = std::min(d, dist(a[l], a[l + 1]));
      return;
    }
    int m = (l + r) / 2;
    merge(l, m);
    merge(m + 1, r);
    std::vector<Point> p;
    for (int i = m - 1; i >= l && a[m].first - a[i].first < d; --i) {
      p.emplace_back(a[i].second, a[i].first);
    }
    for (int i = m; i < r && a[i].first - a[m].first < d; ++i) {
      p.emplace_back(a[i].second, a[i].first);
    }
    std::sort(p.begin(), p.end());
    for (int i = 0; i < p.size(); ++i) {
      for (int j = i + 1; j < p.size() && p[j].first - p[i].first < d; ++j) {
        d = std::min(d, dist(p[i], p[j]));
      }
    }
  };
  merge(0, n);
  return d;
}

分治法还能求两个点作为对交的矩阵的最大面积

三维偏序之陈丹琪分治（仅支持离线查询，还是直接暴力好用~）

如果带更新怎么处理呢？先预处理求出，之后更新一个计算一个更新？（那也不太行呀）

一般地，我们考虑可以考虑 \(k\) 维偏序，设有 \(n\) 个 \(k\) 维向量，\(a_j \leq a_i\) 当且仅当所有的下标都满足小于等于关系，想知道对任意 \(i\) 有多少个 \(j \neq i\) 使得 \(a_j \leq a_i\)。

有复杂度 \(O(n \log^k n)\) 的算法，因此在 \(k > 3\) 时，我们会选择直接 \(O(n^2)\) 暴力解决问题（见下小节）。

  • \(k = 1\) 时，我们直接排序，假设没有相同元素，那么它们排完序之后的位置就是答案，有相同的数字的话可以先合并，也可以用 upper_bound 查找出结果。复杂度 \(O(n \log n)\)
  • \(k = 2\) 时，我们先对第一个坐标偏序，再来一个树状数组，一个个的加入元素，加入之前可以查询结果。这也是求逆序数的操作(如果数据值域范围很大，可以离散化处理一下，仅需对要加入树状数组的那一维离散化，排序可以使用下标排序，就可以避免使用 tuple）。

因此三维偏序是一个空缺的问题，就有大名鼎鼎的 cdq 分治。

模板例题：LOJ P3810，这个题的题解中，有人讲的很好，echo6342：

cdq 分治每次计算前一半对后一半的影响。具体地，假设三维分别是 \(x, y, z\)，先按 \(x\) 排序。分治时每次将前半边、后半边分别按 \(y\) 排序。虽然现在 \(x\) 的顺序被打乱了，但是前半边还是都小于后半边的，所以要是只计算前半边对后半边的偏序关系，是不会受到 \(x\) 的影响的。维护后一半的指针 i，前一半的指针 j，每次将 i 后移一位时，若 \(y[j] \leq y[i]\) 则不断后移 j，并不断将 z[j] 加入树状数组。然后再查询树状数组中有多少数小于等于 z[i]。 最后要清空树状数组（注意清空的时候不能直接清空，而是根据更新的命令，反向一次命令来清空，否则一直开树状数组耗时的），还有就是要去重贼麻烦，还是弃用吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
struct Node {
  int x, y, z, id, w;
  bool operator<(const Node &A) const {
    if (x == A.x) return y == A.y ? z < A.z : y < A.y;
    return x < A.x;
  }
};
// ans[i] 表示 小于或等于 a[i] 的元素个数
std::vector<int> cdq(std::vector<Node> &a, int k) {
  // 先按照 y 排序，免得后面代码写的太麻烦
  std::vector<int> ans(a.size());
  std::sort(a.begin(), a.end());
  // 去重操作
  int last = 0;
  for (int i = 1; i < a.size(); ++i) {
    if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y || a[i].z != a[i - 1].z) {
      int t = i - last - 1;
      for (int j = last; j < i; ++j) {
        ans[a[j].id] = t;
        a[j].w = 0;
      }
      a[i - 1].w = i - last;
      last = i;
    }
  }
  int t = a.size() - last - 1;
  for (int i = last; i < a.size(); ++i) {
    ans[a[i].id] = t;
    a[i].w = 0;
  }
  a.back().w = a.size() - last;
  TreeArray A(k);
  auto cmpy = [](const Node &lhs, const Node &rhs) {
    return lhs.y < rhs.y;
  };
  std::function<void(int, int)> divide = [&](int l, int r) {
    if (r - l <= 1) return;
    int m = (l + r) / 2;
    divide(l, m);
    divide(m, r);
    std::sort(a.begin() + l, a.begin() + m, cmpy);
    std::sort(a.begin() + m, a.begin() + r, cmpy);
    int t = l;
    for (int i = m; i < r; ++i) {
      while (t < m && a[t].y <= a[i].y) {
        A.add(a[t].z, a[t].w);
        ++t;
      }
      ans[a[i].id] += A.sum(a[i].z);
    }
    for (int i = l; i < t; ++i) A.add(a[i].z, -a[i].w);
  };
  divide(0, a.size());
  return ans;
}

k 维偏序（暴力 bitset 优化，分块时间换空间） \(O(\frac{k n^2}{w})\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int N = 4e4 + 2;
// a 是 k * n 矩阵表示 n 个 k 维向量，输出每个小于自身的向量个数
std::vector<int> partialOrder(std::vector<std::vector<int>> &a) {
// 直接暴力不太行，所以需要时间换空间，具体说就是分块。
  int k = a.size(), n = a[0].size();
  using Node = std::vector<std::pair<int, int>>;
  std::vector<Node> f(k, Node(n));
  for (int i = 0; i < k; ++i) {
    for (int j = 0; j < n; ++j) f[i][j] = {a[i][j], j};
    std::sort(f[i].begin(), f[i].end());
  }
  int sn = std::sqrt(n);
  using Data = std::vector<std::bitset<N>>;
  std::vector<Data> bs(k, Data(n / sn + 1));;
  for (int i = 0; i < k; ++i) {
    std::bitset<N> now;
    for (int j = 0; j < n; ++j) {
      if (j % sn == 0) bs[i][j / sn] = now;
      now.set(f[i][j].second);
    }
    if (n % sn == 0) bs[i][n / sn] = now;
  }
  auto getbst = [&](int i, int val) -> std::bitset<N> {
    // 如果求小于或等于的个数，这里要改成 upper_bound 并且要用 INT_MAX，还有最终答案减 1（去掉自身）
    int j = std::lower_bound(f[i].begin(), f[i].end(), std::make_pair(val, INT_MIN)) - f[i].begin();
    std::bitset<N> r = bs[i][j / sn];
    for (int t = j / sn * sn; t < j; ++t) r.set(f[i][t].second);
    return r;
  };
  std::vector<int> r(n);
  for (int j = 0; j < n; ++j) {
    std::bitset<N> now; now.set();
    for (int i = 0; i < k; ++i) {
      now &= getbst(i, a[i][j]);
    }
    r[j] = now.count();
  }
  return r;
}

模板例题：LOJ U66865，可参考 小蒟蒻 yyb 的博客 中的 ppt 实现。其它例题：偏序++

虽然三维偏序问题用 cdq 分治更好，但是用 bitset 暴力过题还是没啥问题的，例如 LOJ P3810

递归算法复杂度定理（算法导论）

递归算法复杂度定理