antontrygubO o old

和 yhp 学长聊天的时候经常会提起 cqbz 的 zxy 神仙。

很久之前翻看 zxy 神仙的博客的时候发现了一篇 zxy的思维技巧

我觉得应该是我看过的所有 OI 相关博客里写的最好的一篇，受此文启发，开了这篇博客记录自己遇到的一些 trick。

开这篇的时候应该是 2023/02/02，第一个版本的东西写的有点杂乱了，而且有些内容其实是有错误的，所以在 2023/07/27 重构了。

如果是算法本身泛化就能做的东西我不会放在这里，会直接放在 /algor 的对应位置。

TODO List

Part 0. 做题ψ(｀∇´)ψ

！！强调！！： 这里的技巧是做题的技巧，不是思维的技巧，要注意区分。

首先是我觉得一个应该被放在首位的东西：

怎么好做就怎么猜结论 —— zjk

拿到题第一个事情还是先读懂题面，手玩样例确认没有问题。

如果一个题太难了不会做，那就再读题。

如果一个题太简单了，一定要再读题。

二者出现在这里的理由都很简单，我不止一次遭遇过因为读错题浪费时间或者是丢掉不该丢的分的惨案了。

然后就是看一看数据范围，大概心里有个底，不一定要按照数据范围来猜做法，可以先想，然后排除或者优化。

出思路这部分个人认为就是最玄学的，也是 OI 最喜欢考察的部分。

如果说这道题有似曾相识的感觉，还是和上面一样，再读一遍确认一下。

然后如果没能看出思路，那么就要开始进行套路枚举了。

简单来说，我们先 bfs 枚举做法，然后对于每个做法 dfs 下去考虑，思考能不能做，问题出在哪里。

然后如果 dfs 有救，在更深层再次 bfs，当然以上的过程都是记忆化搜索，如果所有套路都行不通了，那就枚举新的套路，或者说开始猜做法。

要不然就迭代加深，再来一次，并且摒弃大部分之前的想法，不要想当然的就顺着之前的思路走，一步步确定好再往下。

如果这还是想不到，那确实就只能靠启发和人类智慧了。

一般来说这个过程不要超过 30 分钟，20 分钟是一个比较理想的时长。

如果超过了，那么看看这题暴力值不值得拿，先打个暴力确保有分。

当然这里只是很少的一部分，实际做题的时候还是很容易陷进去出不来的，关于这方面的问题可以看一下：陷入思维空白期时应当做的

等思路确认之后，就是实现部分了，这个就可以看同目录下的：如何有逻辑的实现思路。

调试的时候也按照实现的顺序来调试，会比较有条理。

Part 1. 基础ψ(｀∇´)ψ

Part 1.1. 贪心ψ(｀∇´)ψ

贪心其实是一个比较玄学的问题啊！

很多时候最优策略不是能一眼看出来的，我们需要尝试枚举最优策略，或者说猜。

然后再考虑严谨的证明，如果只是拿不出反例，那就不要认为这个策略是正确的（除非真的是走投无路了不然不要写这类做法）。

常见的策略在这里已经提到了，可以翻阅一下。

这里记录一些不常见的 trick。

『= = = = = = = = = = = = = = = =』

一种拆分的贪心思想：可以按照某种“重要程度”分开考虑，然后对于每一种情况分开考虑，最后直接暴力复合：THUPC2023-pre-A-大富翁
如果一个题，没法很好的通过贪心来快速确定一些必选策略，或者说排除冗杂（也就是有不少特例），此时我们可以考虑直接枚举每一个位置，对他直接通过暴力或者维护信息算答案：CF1801B - Buying gifts，230322C-T2-Brackets。或者是我们就直接考虑 dp：CF1801C-Music Festival (换句话说，我们可以直接考虑在整个状态空间里取最优解，而不是一个劲的考虑局部最优解)
有一个及其重要的思想就是，我们需要找到问题中的“不会更劣”一类的性质，以此作为突破点找到贪心的方向，或者是其它更重要的性质：230813NanJing-Problem，230927NOIP-Learn。

Part 1.2. 构造ψ(｀∇´)ψ

gugugu

UOJ 群文件构造选讲。

Part 1.3. 交互ψ(｀∇´)ψ

交互题出于题目本身的特点，很多时候出不出太多新意，遇到过的都是藏一个什么东西让你问出来，或者通过询问进行操作？

这里就记录了我遇到的所有交互题用到的 trick。

当然大部分交互题都还是需要寻找问题的性质，不能局限于此。

『= = = = = = = = = = = = = = = =』

很多时候可用的询问次数和 \(\log\) 相关，这一般都提示是二进制啊，倍增啊什么的：ABC282F-Union of Two Sets
有的时候要问满足条件的一些元素，我们可以维护答案集合，通过不断的询问，一个个删除不可能成为答案的元素。CF1856D-More Wrong

Part 1.4. 难以归类的小技巧ψ(｀∇´)ψ

！！强调！！： 这里的技巧一定是，难以归类的，一般和算法不沾边，但是是不可或缺的一步转化之类的东西，和做题的技巧要区分开。

Part 1.4.1. 贡献计算ψ(｀∇´)ψ

老生常谈了，这个东西通常是打开问题的第一步。

感觉之后需要第三次总结，再把这里的东西具体化，理论化一点。

『= = = = = = = = = = = = = = = =』

对于一个序列做很多个 independent problem 的时候一般都会要考虑从上一个状态继承，或者是考虑先整体做一遍再计算 ignore 一些操作之后的影响之类的：Least Elements，230203C-T2-排列。
要想清楚，什么东西才会造成贡献，一个位置什么时候合法，什么时候不合法，我们希望能类似拆开限制一样，让各个元素做的贡献尽量的减少对其它元素贡献的影响，这样更方便计算，比如类似 230203C-T4-交换的想法，很多时候也能类似下面 dp 里提到的 Xor-Subsequence (easy version) 一样用来排除不必要的状态，又或者是尝试发现某些看起来对计算贡献有影响的信息实际上对计算贡献没用：230829ChongQing-T2-Dream。
（接上一条）也可以考虑一下，如果我们考虑全局 or 每一段，本身就已经能满足答案的贡献，然后再考虑凑出来之后又出现的新的贡献（前提是开始的时候满足贡献的，拼凑起来之后也能满足贡献）：NOIOnline2022TG-丹钓战，CF1801C-Music Festival
考虑更换贡献的计算方式，选择不那么直观的贡献拆开维护？类似 Manacher 这样，只考虑以一个位置为中心的所有回文串，进一步说这个是钦定一个类似 dp 中“阶段”的基底，找到一个计算贡献的基准。
或者考虑累加影响，批量处理贡献？比如 230201C-T4-回文串，计算答案的时候就是反过来，考虑基准对于所有能产生贡献的点累加一个权值，最后离线在所有点算一下权值即可
也可以对于一个复杂的 \(\sum\sum\min\max\) 这样的式子，我们尝试直接钦定出单个位置的答案，求和之后再推式子ABC290F - Maximum Diameter，不然就是类似上面那样更换计算方式。
对于一个序列或者是什么东西，做多次变换，我们通常可以考虑，原序列对多次操作之后的序列哪些位置会有贡献，贡献是怎么样的 230407C-T3-进化
想清楚一类贡献什么时候会被计算，如果它可以被不同种情况的不同位置更新，是否要考虑钦定只计算某些部分：230117C-T4-子图。
考虑一下修改了一个位置之后，对答案的影响是什么？这里还是以 230201C-T4-回文串为例，这个题确实比较深刻。有些带修改的 dp 也需要用到这样的思想，ddp 算是一种，还有的就是直接暴力更新转移路径上的所有状态，比如 ABC321F-#(subset sum = K) with Add and Erase

Part 1.4.2. 转化ψ(｀∇´)ψ

感觉些东西比较奇妙，也不太好总结。

『= = = = = = = = = = = = = = = =』

切比雪夫距离和曼哈顿距离是可以相互转化的：Gym100739E-Life as a Monster
如果一个最优化问题处理起来十分困难，将其转化为判定问题来求解，记住，大部分时候判定难度远低于最优化：230430C-T3-Square。
当前的式子，当前的一些变量，能不能存在其它等价的，可以方便计算的意义？比如用组合意义转化，或者是用类似 wqs 二分里给式子结合原问题找意义的这种？

Part 1.4.3. 减少限制ψ(｀∇´)ψ

一句话总结这种思想就是，减少耦合度，简化问题。

『= = = = = = = = = = = = = = = =』

类似 CDQ 和点分治的这种“只考虑一种简单情况，其他分治处理”的思想，可以多拿来思考思考。
如果是在对序列做移动操作，我们很难计算贡献，不妨钦定一些元素已经不再移动，或者说考虑还没被移动的元素，进行贡献的分拆计算：AGC032D-Rotation Sort
有一类问题，每次操作 \((i, j)\) 不止会改变 \(a_i, a_j\)，通常还伴有其他的限制，我们一般考虑，想办法通过这些限制找出一个“元操作”，消去/减少限制：ABC296F-Simultaneous Swap
有一类问题，它会要求你按照某个步骤利用某个东西生成某个东西，如果你能尝试维护这里面所谓的“不变量”，那么计算会很方便，当然还有一种想法是转化成图论问题，考虑答案的生成过程，并尝试压缩，合并相同的块/路径，以此达到优化的目的：230509C-T2-Find and Replace。
很多“插入”类的问题都有“相对次序不变的性质”，我们可以从这个方面找到问题的突破口：230414C-T4-ZYB玩字符串
有些时候我们可以考虑忽略部分限制，直接对于一部分限制做完，然后再一一调整满足其它限制，不过在这个过程中通常就可以看出复合后的做法了：Lost Cows（暂无链接）
有的时候甚至可以考虑增加限制来缩减状态，但是仍然保证合法？类似230115C-T3-实验至少不好算，但是至少凑出还可以维护，或者是 230407C-T4-Y老板的别墅这样为了计数方便加入限制的
考虑一下，正着做很麻烦，能否考虑反着做，或者拆开做？
- 更进一步的，如果说我们计算前面的贡献会影响到后面的贡献时，是不是可以考虑倒过来处理贡献：CF264E-Roadside Trees，这也是一种“减少限制”的思想。
是否要考虑分离变量？比如树状数组维护矩阵改矩阵和的时候，比如线段树维护方差的时候。

Part 1.4.4 各种乱搞ψ(｀∇´)ψ

如果是通过打表找规律，找到了 \(k = c\) （常数）的规律，可以考虑把式子中的常数项换成 \(k\) 相关的式子，进而推出通项公式：THUPC2023-pre-B - 拧螺丝
对于一个会跳来跳去，算一下方案数，经过的路径长度之类的问题，可以很容易的想到利用倍增维护：CF1809F - Traveling in Berland。
如果一个问题要你合并一堆东西，而你只会暴力，请务必直接启发式合并：230331C-T2-Favorite Colors。
考虑手玩样例，模拟一下题面的过程看看有没有启发，找找规律试试？比如：220518C-T2-「客星璀璨之夜」这样？或者是类似 2301113C-T4-coin 这种考虑把有联系的东西放在一起，观察到问题的本质？
考虑观察答案的形式，合法解的形状，看看有没有什么启发，比如 Young Maids，考虑一个答案合法后对原问题决策的限制是什么？还是说比如 221025C-T4-罪⼈挽歌
对于一个最优化问题，思考一下，怎么样才能更加优秀，是不是要考虑贪心啊，dp啊之类的做法了？比如 230203C-T3-序列
观察一个看起来啥都没有的问题，要考虑自己手动加上一些限制，写出“不是，就是，一定是，否则”这样的观察，然后考虑这些东西有啥用：230117C-T4-子图。
关于度数的问题，说不定可以考虑使用邻接矩阵存图，有时候会有神奇的效果：230802NanJingT4-Prank

Part 2. 动态规划相关ψ(｀∇´)ψ

建议先阅读 dp 基础，先搞清楚 dp 的本质是什么。

Part 2.1. 关于 dp 本身ψ(｀∇´)ψ

Part 2.1.1. 阶段ψ(｀∇´)ψ

阶段这个东西通常来说都比较套路。

比如线性 dp 就是考虑一个前缀，树形 dp 就是考虑一个子树。

从 dp 本质的角度来说，我们选择阶段，实际上是在选择划分子问题的方式，所以还需要注意，这样的划分方式是否能满足最优子结构（需要结合状态来看）。

有一些题目的阶段选取会比较特殊，在此会有记录：

『= = = = = = = = = = = = = = = =』

如果题目给出的条件无法以线性的顺序作为阶段，比如 Flexible String Revisit 这样要在序列上随机选择的，不然就考虑每一步的代价（这题是从 \(i\) 个不同变化到 \(i - 1\) 个不同为一步），不然就考虑类似状压拆分这种。

Part 2.1.2. 状态ψ(｀∇´)ψ

状态是用来对同一阶段的子问题进行划分的。

通常来说它需要表达的是当前位置的一些限制，比如当前划分了 \(j\) 段，已经选择了 \(k\) 个之类的。

当然限制不仅可以在状态中表达，也可以在决策/转移中表达。

『= = = = = = = = = = = = = = = =』

有些题目需要考虑，在状态中钦定前面一段一定合法，然后只考虑决策时会有变化的部分，这种一般在做转移的时候要小心谨慎，不要漏掉了限制条件。
如果题目中的要素比较多，但是知道一定的信息之后可以推出剩下的信息，我们可以在状态里省去对应的维度：Mobile Service
给一个序列，要求将其分成若干个子段，求某个代价的最大值这一类问题，如果题目没有限制你需要分多少段，可以直接设计 dp 状态为，考虑前 \(i\) 个位置分割成若干段的代价最大是多少：Optimal Partition，任务安排
对于一类对子树整体操作的 dp 问题，设计状态时通常需要考虑子树外的贡献：230626B-T4-Rugby(WIP)
（接上一条）在考虑子树外的贡献的时候，因为不知道内外分别有多少贡献，可以考虑钦定贡献再做转移：230829ChongQing-T4-Light

Part 2.1.3. 决策ψ(｀∇´)ψ

其实也可以把决策说成转移。

决策也是对问题限制表达的一部分，但是相比于状态，它还有一些额外的限制。

为了保证 dp 的正确性，我们的决策需要保证能够不漏的覆盖整个状态空间，如果是计数问题还需要额外考虑不重。

所以很多 dp 题会在这上面下一些手脚，如果发现无法覆盖整个状态空间，或者是出现了重复，一般就两种思路，一种是考虑重新设计，一种是考虑做一些处理。

『= = = = = = = = = = = = = = = =』

对于一类和“顺序”相关的 dp 问题，直接在原序列上选取显然不能覆盖整个状态空间，但是可以注意到有些状态根本就没用，所以我们可以考虑使用 Exchange Argument 对原序列做一次处理（相当于人为的提前做了一部分决策），我们就做到了覆盖整个“有用”的状态空间：Zabuton。
如果 dp 状态直接转移很麻烦，比如那种有关联性的状压 dp，考虑一下等价的转化？2301113C-T4-coin
有些 dp 虽然阶段是下标，但是它转移的时候，为了决策方便，需要更改一下等号左边的下标，方便转移，不然我们不好确定这个决策到底对答案产生了什么贡献：Cleaning Shifts
如果是树形 dp，可以利用 dfs 序的性质，把节点分成两类，用于很好的表达一些祖先关系，很多时候还可以用来减少枚举，直接一步到位：230224C-T4-辣椒
如果在树上使用斜率优化，要记得出子树之后回溯凸壳的状态：Harbingers
期望 dp 在转移的时候可以把期望当成随机变量的一种取值，原理是乘法分配律：Ilya and Escalator，具体可以看期望 dp 的讲稿。

Part 2.1.4. 后效性ψ(｀∇´)ψ

其实我本来想把最优子结构，不重不漏，后效性都分别写出来。

但是其实最优子结构是在设计阶段和状态的部分就考虑到了，不重不漏则是在决策的时候考虑的，而后效性这个，我也不知道怎么分类。

但是能涉及到后效性的 dp 题也不多，百分之八十都应该是转移会成环，此时应当有以下的几种处理方式：

『= = = = = = = = = = = = = = = =』

考虑高斯消元，把所有 dp 方程写成一个线性方程组来解：[HNOI2013] 游走
期望 dp 很多时候要考虑倒推，不然容易因为状态之间的依赖成环，或者因为终止状态不唯一，甚至因为概率不好计算而导致不必要的麻烦：Gotta Go Fast

Part 2.1.5. 转化ψ(｀∇´)ψ

个人认为这是 dp 里面比较巧妙，也是最能用来考出新意的部分。

『= = = = = = = = = = = = = = = =』

组合意义：经典技巧，大致可以泛化成这几类：
- 一个大小为 \(n\) 的集合，它的权值为 \(n\)，可以等价于在集合中选一个数，比如在树上求连通块大小乘积，实际上是考虑把数划分成若干个连通块，每个连通块里选一个数的方案数：230322C-T4-Mushroom
- 一个大小为 \(n\) 的集合，它的权值为 \(\dbinom{n}{k}\)，等价于选出 \(k\) 个不同的数。
  - 如果权值是 \(n^k\) 可以用某种方法拆成若干个 \(\dbinom{n}{i}\) 的和：UOJ667
- 一个大小为 \(n\) 的集合，权值为 \(a^n\)，等价于每选一个数就乘上 \(a\)。
- 组合数 \(\dbinom{n + m}{n}\) 本身的组合意义，可以看作是从 \((0, 0)\) 走到 \((n, m)\) 且只能向右向上走的方案数：AGC002E
对于本质不同子序列，一般都是设 \(dp(i)\) 考虑前 \(i\) 个位置的答案，然后对于当前位置分类讨论即可：230115C-T4-美食
对于一个排列，算一些方案数的计数 dp，他的固有套路就是考虑一个一个插入：230111C-T4-小W与大数

Part 2.2. 关于 dp 优化ψ(｀∇´)ψ

如果不知道该怎么优化了，就尝试写出暴力然后打表看看，这样通常是很有效的，比如凸性，对称性什么的一下就能看出来。

Part 2.2.1 状态优化ψ(｀∇´)ψ

这种优化最常见的部分就是滚动数组，在背包，sosdp，子树合并上都会有应用。

其它的优化就比较有技巧性了，这里记录一些遇到过的：

『= = = = = = = = = = = = = = = =』

230430C-T4-Label 这个题，要通过直接观察 DP 数组本身，找到一大段本质相同的状态，来尝试压缩决策集合以达到优化复杂度的目的。
费用提前计算的思想：任务安排，这个可以理解成“懒操作”的反方向，看起来这是决策优化，其实实际上是改变了 dp 状态本身的定义，所以我也将其归类为状态优化。
有些题，直接定义的状态状态数太大，没法转移，在一些合适的情况下可以考虑交换值域和答案维，将问题转化为一个判定问题，优化复杂度，比如 230811NanJing-T1-Complexity(AGC033D)，有时也会结合到根号平衡的思想。

Part 2.2.2 决策优化ψ(｀∇´)ψ

这种优化其实比较套路感觉，就简单写写吧，例题啥的到对应博客下面看就行。

决策优化，或者说决策集合优化，顾名思义要考虑快速的从决策集合里面获取转移，大约有如下几种方式（这些优化方式当中的 trick 省略了，可以直接到对应页面看）：

『= = = = = = = = = = = = = = = =』

单调队列/单调栈优化 dp，这种一般就是说，内层决策集合的变化是随外层变量单调变化的，我们就可以使用单调队列，直接批量处理外层状态，内层决策集合的枚举就被整合了起来。
斜率优化 dp，这种是单调队列优化 dp 的变种，单调队列里面要求内外层变量不会有乘积，如果有乘积，就考虑分离变量，将方程写成直线的形式，维护凸包来进行优化。
数据结构优化 dp，这种就是说你发现决策集合比较特殊，可以直接通过数据结构维护来转移，一般可以把枚举的复杂度从 \(O(n)\) 降到 \(O(\log n)\) 左右。
四边形不等式优化，这种就是对于代价函数比较特殊的情况，有特殊的转移，当然它下面还细分了决策单调性优化，决策单调性就要考虑是否会自身转移自身，并选择合适的做法。
Slope trick，这种的 dp 和代价函数通常是凸的，我们可以考虑维护转折点，维护值或者维护值的差分（斜率）来把方程的转移转化成别的更好做的形式。

Part 3. 数学相关ψ(｀∇´)ψ

Part 3.1. 性质相关ψ(｀∇´)ψ

Lcm 的本质就是，对于所运算的数质因数分解，考虑每个因子出现的最高次幂，然后乘起来：230331C-T3-Exercise。
二进制下加一的本质就是，找到低位的第一个 0，变成 1 之后把之后的 1 全部变成 0：01Trie 维护全局加一.
如果一个问题在某些限制为质数的条件下比较好做，但是当前的限制是合数，我们可以考虑用 exCRT 一类的东西合并答案，转化成更简单的问题。
卢卡斯定理似乎可以被看作 P 进制数的一些引用，这个是某 MOer 教我的，某场 ABC 用到了，但是我没改，有时间来补一下。

Part 3.2. 计数ψ(｀∇´)ψ

对于下标里有限制的，通常可以拿出来考虑，这样也许会简化计算:ABC297F-Minimum Bounding Box 2
对于一些多次求和的问题，我们是否可以考虑交换求和顺序？当然交换的时候要注意下标的限制：ABC297F-Minimum Bounding Box 2
那种限制比较多但是可以分类的，或者是容易算重的问题，都可以考虑容斥原理，当然使用的时候要想想能不能化简以满足复杂度，不然就要换一换其他做法，比如 dp：230411C-T3-逆序对
如果对于一个计数问题，推出了它的充分不必要条件，导致不必要的部分可以尝试抽象条件，利用容斥算掉：230418C-T1-序列。

Part 4. 图论相关ψ(｀∇´)ψ

Part 4.1. 连通性问题ψ(｀∇´)ψ

对于一个有向图连通性问题，不止可以考虑 Tarjan，在一定条件下还可以考虑先连出反向边，加边之后变成无向边，可以使用 dsu 维护：ABC295G-Minimum Reachable City
通常对于一个联通块，维护了联通块信息，考虑合并的时候，会用到启发式合并，不然复杂度容易寄掉：230418C-T2-图。
对于一个连通性问题，dfs 树是一个很有力的工具，我们可以把许多问题拆分到 dfs 树上，用类似 Tarjan 的思想来处理问题：CF19E-Fairy
无向图有耳分解当且仅当它是边双连通的，这个结论有一个很大的用处就是可以辅助我们找到 dp 的转移：CF1155F-Delivery Oligopoly
有向图必经边可以通过出边标记的方式来求：230811NanJing-T2-Changes(ARC092F)，不过更好的方式是支配树？

Part 4.2. 树上问题ψ(｀∇´)ψ

树的括号序可以表达的不止有子树关系，还可以表达距离关系（甚至可以带权值）：CF1149C-Tree Generator™
轻子树的大小之和总数级别为 \(O(n \log n)\)，这在一些需要在树上合并的问题中很常用，可以用于优化复杂度（dsu on tree）：CF1856E2-PermuTree (hard version)

Part 4.3. 路径相关ψ(｀∇´)ψ

分层图最短路的时候，如果发现连边过多，可以考虑把这些边归类，看能不能新建一层，用一条边来表示：HDU5582-Journey of Taku

Part 4.4. 基环树ψ(｀∇´)ψ

基环树相关问题有一个套路，先把树的部分做了，然后考虑合并到环上来做：BZOJ1950-Link

Part 5. 数据结构相关ψ(｀∇´)ψ

Part 5.1. 转化ψ(｀∇´)ψ

对于一个比较复杂的，动态维护的问题，我们可以尝试利用 CDQ 分治，将动态的问题转化为静态的，其原理是利用分治的思想将一堆动态问题拆分成几个小的静态问题。
有一类问题，虽然是区间操作，但是因为多次操作之后会有很多“无用”的操作，此时可以在区间操作中加一个剪枝优化，以达到类似单点改复杂度的效果：区间开根号，维护区间和，区间取模，维护区间 Max，[六省联考 2017] 相逢是问候。

Part 5.2. 明确需要维护的信息ψ(｀∇´)ψ

维护的信息的区别会导致代码实现复杂度的区别。

如 Buy tickets 这一题，如果直接维护整个序列会很麻烦，需要到处删除加点之类的，如果这题我们选择了“维护空位”，问题就变成了简单的线段树二分了。

Part 5.3. 选择合适的数据结构ψ(｀∇´)ψ

数据结构的不同往往会直接决定代码实现复杂度和你的心态。

如果一个问题一看就是比较显然的 XXX 板子，但是实现难度确实太高，我们可以考虑，在当前的限制下，存不存在另一种更巧妙的维护方式？比如线段树二分+区间 qmax，可不可以直接先 sort 然后类似对顶的两个 set 维护两个部分？CF1801B - Buying gifts

Part 5.4. 维护方式(模型)ψ(｀∇´)ψ

对于维护的复杂的信息，通常我们需要考虑拆开进行维护，使得不满足一些可以维护的性质的信息变得可以维护（也是复合和分拆的思想）：区间方差，也可以说成是分离常量和变量，将变量分类维护。
对于一些没有明显的结合律的信息，是不是可以考虑多添加一些信息，来使得这个信息具有结合律？比如说线段树当中的类区间最大子段和问题。

Part 6. 字符串相关ψ(｀∇´)ψ

有的时候，在确定字符集大小和操作长度可行的时候，我们可以使用 bitset 来支持匹配操作：230411C-T4-小王献歌

最后更新: November 6, 2023