Algorithms

算法 trick 的记录。 系列前作：https://www.luogu.com.cn/article/yc9w22em 拆贡献！拆贡献！交换维度！交换维度！时间逆流！时间逆流！操作顺序反演！操作顺序反演！递推！递推！分离常量！分离常量！不同的项分开算！ 优化一些代数式计算的复杂度时，最简单常用的技巧就是试着拆开，然后分离常量和变量，将不同类项分开处理。而当你推不出一些式子时，可以放弃推式子而使用递推。交换求和顺序/交换 DP 转移顺序/维度是破解循环依赖，找到好的计算顺序的方法，这和拆贡献是相关的：拆贡献其实就是变换了统计的第一维度。从按照整体的统计变成按照单个元素统计。 双指针就是“在不合法和不优之间的境界线上游走”，同时也是“一种扫描线”，并且是“在复杂度允许的情况下，枚举一定量信息以确定更多条件”的体现。 而“枚举一定量信息”在 DP 中也很常用。DP 的经典套路就是随便乱设状态，加入信息直到能够转移为止，然后利用种种洞察和优化去掉一部分维度，优化转移直到时空复杂度达标。 在做任何题的时候，第一步考虑性质刻画。无论是操作的性质还是维护信息的性质。性质就是限制，能够帮你找出正解。 一个好的性质刻画也很重要。一个愚蠢的性质刻画会极大地妨碍你做题。所以如果你觉得性质刻画太笨，就试着简化。 “信息学”的本质就是对于信息的处理。算法对于复杂度的优化本质上是减少不必要的对信息的处理（计算）。所以当你试图确定复杂度或者优化复杂度时，不妨思考一下“这个题，至少需要处理哪些信息？如何避免处理不必要的信息？” 信息即向量，操作即矩阵。 写了线性代数大学习，你应当能知道这点。有许多操作都是线性/仿射的，可以写成矩阵。从而拥有结合性，可以用快速幂或者线段树等方法处理。 孤链压缩权值线段树/01 trie。线性空间复杂度，从此整数可重集再也不用平衡树。 线性筛线性预处理积性数论函数。要点在于筛 n = i * p 时用到的 p 和 i 满足 p 不大于 i 的最小质因子。比埃筛更好写。 以后再也不要 naive 地 $O(n \log n)$ 算 d(i) 了。 利用单调性等等贪心性质简化问题。 有交不优 => 钦定末尾。 有时二维问题按第一维排序，而后第二维更小就一定更优所以无脑排除一些。剩下的就满足二维偏序（相当于利用贪心性质额外制造了一个维度上的单调性。这里的贪心性质是“a 被 b 包含 => b 的所有解都不劣于 a 的对应解/a 能干的所有 b 都能干”） 两种证明贪心的策略： 局部上，交换论证/调整法：调整一定能导出不劣的解。 整体上，必要性 => 充分性：我们至少需要多少操作，然后让这些操作发挥最大的效益。 增量更新并不要求旧的答案一定是新的答案。在旧答案总数很小时，可以暴力枚举它们判断它们是否是新的答案。或者，如果容易确定哪些不是新的答案，排除它们即可。 对于一些非常复杂的操作，可以考虑寻找不变量。常见的不变量常常和奇偶性或者两类元素的差有关。因为总和是容易变的，但是有时对于两类东西的作用是相同的，就可以被作差消去。 当操作是对两个相邻元素（或者类似的，一个元素附近的几个元素）时，这样的关于奇偶性或者奇偶下标的元素的差的不变量比较容易出现。 不变量和另一种思想紧密相关，即状态而非过程。在很多贪心或者博弈论的题中，常常有复杂的流程模拟，直接陷进去就做不出来了。 这时可以考虑最终状态或者解的性质，有时能够得到非常简洁优雅的结果。就像解方程一样。 ...

问题 给定原串 $s$ 与模式串 $t$。其中模式串可能含有一些 ? 字符（而原串没有），问号可以与任何字符匹配。问模式串与 $s$ 中哪些位置匹配？ 形式化的： 我们称两个字符串相等，当且仅当： 它们长度相等 对于任意一个位置 $i$（$0 \leq i < \mathrm{len}$，$\mathrm{len}$ 是两个字符串的长度），两个字符串在这个位置上的对应字符相等，或至少一个字符串在这个位置上的对应字符是问号。 现在的问题是，求出所有的 $0 \leq i \leq \operatorname{len}(s) - \operatorname{len}(t)$ 满足 $s$ 从 $i$ 开始（包含 $i$），长度为 $\operatorname{len}(t)$ 的子串与 $t$ 相等。 下设 $n := \operatorname{len}(s), \; m := \operatorname{len}(t)$。 bitset 做法 bitset 能够简单高效的解决这个问题，复杂度为 $O(nm/w)$。 具体的：对于每种字符 $c$，我们维护一个长度为 $n$ 的 bitset。bitset 的下标为 $i$ 的位置为 true 当且仅当 $s_i = c$。 注意到，假如 $i$ 是一个匹配的起始点，这意味着 $s_{i+j} = t_j$ 对所有 $0 \leq j < m$ 的 $j$ 成立。反过来： ...

做到了 ABC448E，感觉很精妙。 题目中有个部分是模意义下等比数列求和。那么来讲讲它的几种做法。 公式 直接套公式。 $$ \sum_{i=0}^n a^i = \frac{a^{n+1}-1}{a-1} $$然后用逆元。不讲。 如果等比数列不是从 1 开始的，提取首项为公因数即可。下面所有讨论都默认 1 为首项。 更好的方法 公式法需要逆元，在逆元不存在时就寄了。而恰好，448E 的模数不是质数。 我们有几种方法来处理这个情况 下文定义 $$ f(l, a) = \sum_{i = 0}^{l-1} a^i $$分治求和 洛谷已经有篇文章讲过这种手法了。我在场上推出来也受到了它的启发。 大概来说，我们将序列平均分为两部分。 $$ f(l, a) = \begin{cases} (1+a^{l/2})x, \; l \text{ is even}\\ x+a^{(l-1)/2}(ax+1), \; l \text{ is odd} \end{cases} $$其中 $x := f(\lfloor \frac{l}{2} \rfloor, a)$。 这样，做分治再套快速幂就可以以 2log 复杂度解决。不过这样不够优秀。 两种优化的分治 维护幂信息 注意到每层递归重算快速幂非常不优。我们在计算 $f(l, a)$ 时顺便维护 $a^l$，在计算完 $x$ 之后将 $a^{\lfloor \frac{l}{2} \rfloor}$ 平方就得到 $a^l$。 ...

引入 给定字符串 $S$ 与模式串 $P$。问 $P$ 的最长的是 $S$ 的子串的前缀的长度。 我会暴力！ $O(nm)$，非常显然。不讲。 喜欢哈希的小朋友们你们好啊！ 注意到答案具备单调性。于是我们使用二分，外加哈希来检验。 复杂度 $O(n\log m)$，其中 $n$ 是 $S$ 的长度，$m$ 是 $P$ 的长度。 已经很优秀了，但是还不够，毒瘤出题人出了 $n=m=3\times 10^7$ 的数据范围！ 等价重写 Hash 的算法相当于二分匹配前缀长度，然后枚举前缀匹配起始点。 重写为另一种等价的形式：枚举前缀匹配的起始点，然后二分产生的匹配的长度。 现在，Hash 的问题在于每次重新二分一看就非常不优。 当然我不是让大家写分散层叠（分散层叠也完全用不上）。但是我们获得了一些优化的可能。 包的 假设现在我们在一个匹配起始点 $i$，有一个长度为 $l$ 的匹配（意味着匹配的结束点在 $e = i + l - 1$）。 考虑一个起始点在 $i$ 之后的匹配：假设起始点为 $j$。 有两种可能： $j \leq e$ $j > e$ 我们先处理所有第一种情况，然后我们重置 $i = e + 1$ 就可以继续处理第二种情况。 注意到第一种情况具备非常神奇的特性：$[j, i + l)$ 这段下标区间内 $S$ 的子串，等于 $P$ 长度为 $i + l - j$ 的前缀，而同时，当前起始点在 $i$ 的匹配中，与这部分对齐的一段后缀也等于这段子串！ ...

考虑这么一个题目： 维护整数多重集，支持插入删除，查询全局 xor 和以及全局加一。 如果不考虑全局加一，就是唐题。不过全局加一和异或本质不兼容，比较难搞。 本文介绍的就是用以解决这一问题的技巧。 考虑维护一棵 01 Trie。与普通的用于按位贪心的 Trie 不同，这棵 Trie 按照从低位往高位的顺序。 简单来说，根节点是从低往高第 0 位，是一个超级源点。它的两个孩子是从低往高第 1 位，位权为 1，这两个孩子的孩子（即深度为 2 的那一层节点）的位权为 2，以此类推。 插入、删除和普通 01 Trie 相同。 查询全局 xor 和也比较好做。我们在每个节点上维护 count（子树中的元素计数）和 xor_sum（子树中元素的异或和）。 加法是重点。 注意到最低位为 0 的元素加一之后最低位为 1，而最低位为 1 的元素加一之后最低位为 0，并产生一个进位。 那么从根节点出发，先交换两个儿子，然后递归操作那个本次操作前当前位为 1 的子树。 结束了。 扩展：全局异或上一个数 考虑维护全局懒标记：Trie 中的一个值 v 的实际值是 v xor tag。 全局异或就变成了对 tag 的简单更新。 现在考虑如何在有 tag 的情况下做全局加一。 很简单：套用之前交换子树和递归进位的逻辑。不过，注意 Trie 中当前位为 1 的子树未必是真实产生进位的子树，因为 tag 的当前位可能为 1，这时，Trie 中的 1 子树的真实值为 0，反而是 0 子树的真实值为 1。

省流：gemini 3.1 Pro 对这个经典难题提出了一个优于暴力的做法。 区间加区间异或和怎么做？ 具体的，你需要维护一个整数数组，支持两种操作： 将一个连续区间内所有元素加上一个整数 查询一个连续区间内的元素的异或和 这个题有任何比较好的做法吗？ 这是一个在算法竞赛（如 Codeforces、Luogu）中非常经典的高级数据结构难题。 区间加（Addition）和区间异或和（XOR Sum）在本质上是“不兼容”的。因为加法会产生进位（Carry），一个加法操作可能会同时改变多个连续的高位，这导致传统的线段树（Segment Tree）无法在 $O(\log n)$ 的时间内合并和下传 Lazy Tag。 目前解决这个问题最通用且高效的经典做法是：分块（Square Root Decomposition / Block Decomposition），结合按位拆分与二分查找。 以下是详细的做法和原理解析： 核心思想：按位拆分 + 余数定理 我们要查询区间异或和，实际上等价于：对于每一位 $k$（$k \in [0, 30]$），统计区间内该位为 $1$ 的数字个数。如果个数为奇数，那么异或和的第 $k$ 位就是 $1$。 假设一个数字原来是 $x$，被加上了 $v$。那么 $x+v$ 的第 $k$ 位是否为 $1$，完全取决于它们对 $2^{k+1}$ 的余数。 具体规律如下： 设 $M = 2^{k+1}$， $H = 2^k$。 那么 $(x + v)$ 的第 $k$ 位为 $1$，当且仅当： $$ (x \bmod M + v \bmod M) \bmod M \ge H $$如果我们将 $y = x \bmod M$ 看作原数组的属性， $V = v \bmod M$ 看作懒标记（Lazy Tag），因为 $y \in [0, M-1]$ 且 $V \in [0, M-1]$，上述条件其实等价于 $y$ 落在了两个连续的区间内： ...

你的调整法证明可能假了！ 看到 P1012 被升蓝，以及 Register_int 的帖子，感慨良多。 事实上，我发现自己之前许多调整法/交换论证的证明是假的。所以写这篇文章来整理交换论证相关。 邻项交换 若对于相邻两项 $x, y$，让 $x$ 在 $y$ 前面更优，我们称 $x < y$。 很多证明可能到这一步就停止了。然而这是错误的。仅仅具备这样的性质，并不能保证“对于任意相邻两项 $x, y$，其中靠前的 $x$ 满足 $x < y$”的序列是唯一的。 简单的反例：$x < y, y < z, z < x$。这时 $(x, y, z)$ 与 $(z, x, y)$ 均满足条件。 不同的序关系 oi-wiki 有所提及：https://oi-wiki.org/math/order-theory/ 重点在于定义的那些性质，以及全序、偏序、严格偏序、弱序、严格弱序等不同种类的序关系。 众所周知，如果把 $\lambda x . \lambda y . \; (x\leq y)$ 放进 std::sort 中，很有可能会得到死循环的结果。因为它要求严格弱序，即需要非自反性和非对称性。简单来说，$x < y \text{ and } y < x$ 与 $x < x$ 两个性质都是恒不成立的。同时，严格弱序还要求不可比性是一个等价关系（即满足自反性、传递性和对称性，如果不可比性不是等价关系，则这只是严格偏序而不是严格弱序）。 ...

亲手实现一个正则引擎！ 众所周知，一类经典的自动机是有限状态自动机。它们识别的语言是正则语言，而正则表达式能够匹配的字符串的集合也是正则语言。 （如果你之前没有了解过，询问 AI 或是使用搜索引擎都很适合快速了解） 导数法 要匹配一个正则表达式，最经典的方法就是构造对应的 NFA，然后通过一些手法转化为 DFA。但这太复杂了。有没有更简单的方法呢？ 有一种被称为“导数法”的方法。 思想非常简单：我们将构造出的 DFA 编码为一个正则。这样，转移之后相当于产生了一个新的自动机，也就是一个新的正则表达式。 原始正则表达式是 $r$。那么，$r$“吃掉”一个字符 $c$ 之后产生的表达式 $r'$，能匹配的所有字符串就是所有满足 (match? (cat c s) r) 的字符串 $s$。 读者可以自行思考一下导数公式。 我想用代码表示是最清晰的。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 (define (derive re c) (match re [(Void) (Void)] [(Eps) (Void)] [(Dot) (Eps)] [(Chr ch) (if (char=? ch c) (Eps) (Void))] [(Alt e1 e2) (make-alt (derive e1 c) (derive e2 c))] [(Cat e1 e2) (if (nullable? e1) (make-alt (make-cat (derive e1 c) e2) (derive e2 c)) (make-cat (derive e1 c) e2))] [(Star e) (make-cat (derive e c) (Star e))])) 导数法将是我们使用的核心算法。 特性与抽象语法 我们将实现支持连接（cat），选择（alt）与闭包（kleene star）三种特性的正则表达式。同时添加“任意字符”（Dot）这种有用的语法糖（为了辅助包含匹配）。 ...

简单技巧。实用的小 trick。 一般而言多维偏序（比如大于等于 3 维的偏序）做法是 CDQ 分治。但是当维度比较多（比如 5D 以上）时 CDQ 会极其难写，并且带有很多 log，实际效率很劣。 bitset 能够以 $O(\frac{n^2d}{w})$ 时间和 $O(\frac{n^2}{8})$ 空间解决这类问题。 方法非常简单：高维偏序，要求我们统计满足在每一维度上的属性都被当前元素偏序的元素的集合。“在每一维度上都被偏序”就是每个维度上的独立偏序条件的逻辑与，在集合上，对应的就是交集。 这可以用 bitset 维护，于是做完了。 具体的，我们设 ans[i] 是一个 bitset，维护被 i 偏序的元素的集合，第 j 位为 1 代表 j 被 i 偏序。那么，我们枚举每个维度，设 f[i] 是这个维度上被 i 偏序的元素的集合（同样，第 j 位为 1 代表 j 在这一维度上被 i 偏序。），令 ans[i] = ans[i] & f[i] 即可。 例题：【模板】三维偏序/陌上花开。以及 CF1826E Walk the Runway，等等。 放一个后面那道题的代码： 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 56 57 58 59 60 61 62 #include <bits/stdc++.h> using namespace std; int m, n; array<int, 5005> p; array<bitset<5005>, 5005> e; array<long long, 5005> ans; array<array<int, 5005>, 505> r; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> m >> n; for (int i = 1; i <= n; ++i) { cin >> p[i]; } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { cin >> r[i][j]; } } for (int i = 1; i <= m; ++i) { vector<pair<int, int>> tmp(n + 2); for (int j = 1; j <= n; ++j) { tmp[j] = {r[i][j], j}; } sort(tmp.begin() + 1, tmp.begin() + n + 1); bitset<5005> cur; cur.set(); int banned = 0; for (int j = 1; j <= n; ++j) { while (banned <= n && tmp[banned].first < tmp[j].first) { cur[tmp[banned].second] = false; banned++; } e[tmp[j].second] |= cur; } if (i == m) { for (int id: views::values(tmp)) { e[id].flip(); for (int pre = e[id]._Find_first(); pre <= n; pre = e[id]._Find_next(pre)) { ans[id] = max(ans[id], ans[pre]); } ans[id] += p[id]; } } } long long final = 0; for (int i = 1; i <= n; ++i) { final = max(final, ans[i]); } cout << final; return 0; } 分块优化 三维偏序模板直接套 bitset 会爆空间。解决方法是分块处理：将所有元素划分进一个个大小为 B 的块里。 ...

如题，一种 lisp 列表的增强版，支持 $O(\log 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 #lang racket/base (define (length-geq? l n) (let loop ([cur l] [len 0]) (cond [(>= len n) #t] [(null? cur) #f] [else (loop (cdr cur) (add1 len))]))) (struct alist (roots) #:transparent) (struct single-tree (root size) #:transparent) (struct tree-node (val l r) #:transparent) (define (alist-cons head l) (let ([rt (alist-roots l)]) (if (length-geq? rt 2) (let ([a (car rt)] [b (cadr rt)] [rest (cddr rt)]) (if (= (single-tree-size a) (single-tree-size b)) (alist (cons (single-tree (tree-node head (single-tree-root a) (single-tree-root b)) (add1 (* 2 (single-tree-size b)))) rest)) (alist (cons (single-tree (tree-node head #f #f) 1) rt)))) (alist (cons (single-tree (tree-node head #f #f) 1) rt))))) (define (alist-car l) (let ([head (car (alist-roots l))]) (tree-node-val (single-tree-root head)))) (define (alist-cdr l) (let ([head (car (alist-roots l))] [rest (cdr (alist-roots l))]) (if (= (single-tree-size head) 1) (alist rest) (let* ([root (single-tree-root head)] [lson (tree-node-l root)] [rson (tree-node-r root)] [size (arithmetic-shift (single-tree-size head) -1)]) (alist (cons (single-tree lson size) (cons (single-tree rson size) rest))))))) (define (get-binary x) (define width (integer-length x)) (define res (make-vector width #f)) (let loop ([i (sub1 width)]) (when (>= i 0) (when (not (zero? (bitwise-and 1 (arithmetic-shift x (- i))))) (vector-set! res i #t)) (loop (sub1 i)))) res) (define (access-in-single-tree p idx) (define width (integer-length idx)) (define bin (get-binary idx)) (let loop ([i (- width 2)] [cur p]) (if (>= i 0) (if (vector-ref bin i) (loop (sub1 i) (tree-node-r cur)) (loop (sub1 i) (tree-node-l cur))) (tree-node-val cur)))) (define (random-access l pos) (set! pos (add1 pos)) ;; 0-base => 1-base (let ([roots (alist-roots l)]) (let loop ([cur roots] [i pos]) (let ([rt (car cur)]) (if (> i (single-tree-size rt)) (loop (cdr cur) (- i (single-tree-size rt))) (access-in-single-tree (single-tree-root rt) i)))))) (define (set-in-single-tree p idx v) (define width (integer-length idx)) (define bin (get-binary idx)) (let loop ([i (- width 2)] [cur p]) (let ([org (tree-node-val cur)] [lson (tree-node-l cur)] [rson (tree-node-r cur)]) (if (< i 0) (tree-node v lson rson) (if (vector-ref bin i) (tree-node org lson (loop (sub1 i) rson)) (tree-node org (loop (sub1 i) lson) rson)))))) (define (random-set l pos v) (set! pos (add1 pos)) (define res (let ([roots (alist-roots l)]) (let loop ([cur roots] [i pos]) (let ([rt (car cur)]) (if (> i (single-tree-size rt)) (cons rt (loop (cdr cur) (- i (single-tree-size rt)))) (cons (single-tree (set-in-single-tree (single-tree-root rt) i v) (single-tree-size rt)) (cdr cur))))))) (alist res)) ;; tests (define a (alist '())) (set! a (alist-cons 3 a)) (set! a (alist-cons 5 a)) (displayln (random-access a 0)) (set! a (alist-cons 7 a)) (set! a (alist-cons 9 a)) (displayln (random-access a 2)) (set! a (random-set a 2 'a)) (displayln (random-access a 2)) (displayln (random-access (alist-cdr a) 1)) 概述 一种基于完美二叉树以及斜二进制分解的结构。lisp 列表的上位替代，支持 $O(1)$ 的 car/cdr/cons，$O(\log n)$ 的随机访问修改。完全可持久化，支持不可变性和结构共享。 ...