OI 思维技巧
我试图将所遇见的抽象、感性之事物具体化，理论化。
这便是一步微不足道的尝试，经过不算长的时间，我发现，想要做到绝对的完美是困难的。
尝试做出统一化的结果是困难的，不过总是要做尝试的，不然永远没有机会了。
我很容易因为某个 trick “并不实用”，从而对我曾经所写下的文字感到烦躁，厌恶。
实际上当 trick 失去时效性之后，了解到 trick 时的感受就会消散不见，这很容易让我误以为某个 trick 是没用的。
更发现有些东西如果想要规约，实际上非常牵强，它只是想法类的东西。
经历过多次重构，修改，目前决定将本文分为两个部分，Tricks 和 Minds
并且在其它地方记录的东西也可以再次放入，没有必要说这种具体放在哪里的鸡毛蒜皮的小细节都需要关心。
还有就是，有些事情不上手做的话，是确实会感到焦虑的，所以焦虑的时候不妨立马开始做事。
最后，别想着一下就能把所有事情都做的十全十美，那是不现实的。
现在所要做的，就是把以前做过的所有题目中的思考方式以及技巧区分开来，目前进度 2023/01/01。
受 zxy的思维技巧 启发，开了本篇博客进行一些技巧的记录。
开篇：2023/02/02，第一次重构：2023/07/27，第二次重构：2023/10/18
前两次的整体架构/内容或多或少的让我有不满意的地方，不过说是“无用”可能更为妥当。
仅仅是对 trick 的形式化记录是没用的，遇到了之后也只能思考：“是不是这个啊？这么做是不是对的？”。
Trick 应当是在进行过从定义开始的演算和推理过后，用于处理所求问题的一个工具，它不应当用于“寻找”思路，而是该用于“铺设”和“连接”思路。
以此为出发点，所整理的 trick 应当包含如下部分，换句话说这是本篇博客中所有内容应当遵守的准则。
- 清晰的描述，换句话说尽量不要使用“某些，麻烦，看看有没有什么启发”一类的语言，取之以具体的例子或更加形式化的描述，如“会对未计算的状态造成变量次数更高，复杂度更高的贡献”。
- 前置条件/应用前提：如“在正向处理需要维护诸如前缀最值，前缀历史最值等复杂信息的情况下”。
- Trick 本体：如“考虑从倒着处理，从终态开始计算答案。”，这部分也应当包含相关的处理/维护方式，如“使用单调栈维护 Next Greater Element”，“选择区间中最小的作为代表”。
- 为什么这么做更容易，更自然？：“终态的唯一性使得它相比于不唯一的初态更容易计算贡献”，“这样能够减少实际有效状态数，进一步降低复杂度”。
可以说简单一点，但这些要素不能缺少。
但如果只是比较小型的记录，比如说某一步可以考虑维护的方式，就可以省去这些内容。
目前正在重构中，分类仍旧遵循前两个版本的方式。
感谢 kk 给出的建议。
等过段时间实践的差不多了再来更新一下，应该如何观察，思考题目，如何使用这些 trick。
目前仍然保留了上一个版本的记录：Old version
基础思考方式ψ(｀∇´)ψ
贡献计算ψ(｀∇´)ψ
当我们需要对一个序列做多个 Independent Problem（譬如，对于每个 \(i\) 求包含它的最长好区间长度），而直接暴力处理复杂度不能接受时，我们有以下几种处理办法：
- 考虑直接从上一个状态继承，并做一些修改：比如换根 DP，Least Elements，230203C-T2-排列，这两个题都是直接继承之后考虑加入的这个数的贡献。
- 考虑整体做一遍，然后考虑如果我们忽略掉这个位置，会有什么变化：比如扣除某个数的背包的维护前后缀做法。
- 就是直接对每个问题分别求解，通常来说会有一些信息，我们可以将其拼凑起来得到某个问题的答案：231023B-T2-Firework。
对于一些带修改的问题，如果我们不太好使用数据结构之类的东西维护，不妨先考虑一下，当我们对某个位置修改之后，它对哪些答案会有影响，影响是什么。
当然其实这个思想和上面那一条的第一小条是类似的，都是考虑形如“变化”的东西。
这样的题比如：230201C-T4-回文串，ABC321F-#(subset sum = K) with Add and Erase。
前一个题大概是考虑修改一个位置之后对回文半径内的位置的贡献，后一个题就是可删除背包的直接删除做法。
这个带修改也可以看作是需要支持动态加入，所使用的技巧也是差不多的，都是考虑新加入的贡献。
这个题就是考虑，当我们加入一个元素的时候，有哪些元素和这个元素组成的点对是好的。
一个比较常见的情形是，如果直接暴力计算贡献，或者枚举整个候选集合，复杂度难以接受。
很自然的想法是考虑更改计算贡献的方式：
- 对于某个整体计算贡献，可以考虑转为对单个元素的贡献进行考虑，形象的理解是一个点可能被多个合法区间覆盖，我们要做的是考虑把它对每个合法区间的贡献算出来；
- 对于一个贡献，将其拆分成不同来源的多个部分，使得我们能找到一个新的通用基准对一些位置方便的计算，这个说来比较抽象，你也可以将其理解为一种形如分离变量的方式。
[TODO) 这样的题暂时忘了有哪些比较合适做例子，暂时放置
对于一个以某种规则（比如 rotate 之后再交换某几个特定位置）进行变换的序列，如果我们想要求出多次变换过后的序列，一种常见的处理方法是考虑每个位置的贡献而不是直接整体处理，这样我们需要处理的问题规模相对要更小。
比如：230407C-T3-进化，可以注意到贡献形如杨辉三角形，所以不妨考虑最后的每个位置能对最初的那个位置做多少贡献。
如果贡献/信息的形式表现为若干个区间，但直接计算并不是那么优秀的时候，通常我们会有以下考量：
- 考虑将其变成“不包含即相离”的情况，具体来说通过使用调整法将相交变为包含，或者是考虑证明满足条件的形式一定是不交的；这样，区间之间的关系将会构成一棵树，处理起来会方便很多，当然也不一定要按树的形式考虑，也可以考虑贡献覆盖；例子有：230923NOIP-Se
- 对区间进行排序，将贡献挂在左/右端点上进行计算（因为我们通常从左向右扫，所以一般按右端点排序，贡献挂在右端点上进行计算）:230902CQ-T2-Poker
有时候我们并不需要直接计算答案，我们可以通过答案来计算条件，并在满足限制的条件对应的答案中找到最优解。
这一般适用于答案较小或者是需要计算答案的位置较多的时候。
一个例子是 dp 中考虑交换值域和答案维度，这通常在答案较小值域较大时使用，用于减小空间开销，最好的例子是：AGC033D-Complexity
另一个例子是，当答案存在单调性，并且以一定连续段形式存在时，我们也可以考虑记录答案，求出限制。
比如 231106NOIP-T3-Stair，这个题和 Complexity 有点像，也是考虑 dp 一个答案对应的最远/近位置，然后枚举答案更新贡献。
还有就是 231103NOIP-T3-Follow，这个题则是答案存在普通的单调性，但是需要对于多个位置求答案，可以直接枚举答案，考虑二分出这个答案覆盖的区间。
有一类问题的贡献形如一个二元组 \((r, q)\) 的形式，表示，当满足限制 \(r\) 的时候，将获得 \(q\) 的贡献。
这类问题可能会有多个以某种方式连接的这种限制，举几个例子：
一种是 大家都喜欢百合咲美香，不是吗？ 这样的。
因为实际上你注意到，对于是否要选择一个旅行伙伴这件事，我们不需要立马做出决定，在体力不够用的时候再贪心的取最优的就行。
还有一种是，20230926NOIP-Learn，也是可以维护一个当前已经可以选的集合，只有到不够用的时候才拿出来用，因为你反正就算知道哪些最后能选，全部堆上去，能到达的位置也是不会变化的，所以也是用一种延后考虑的思想来处理。
不过这个限制关系构成一个 DAG 的样子，所以我们是用队列维护，前一个题需要贪心是因为对于每个贡献，不选择也是会有负贡献的，而后一个题并没有这样的条件。
减少限制ψ(｀∇´)ψ
一种常见的减少问题限制的方式是做一个脚踏实地的人。
怎么说？就是我们对于一个多重限制，最自然的想法应该是先分别考虑每个限制，再将其耦合起来。
解决耦合度低的问题通常是更加容易的，耦合度可以这么理解：\(a_i + a_j\) 的耦合度远远小于 \(a_i \times a_j\)，因为分离它们更加容易。
举个例子，三维数点，实际上就是这种思想的体现，我们通过 CDQ 分治的特性将几个变量分开处理，通过排序消除某个限制对另一个限制的约束，这里看起来没有最后一步耦合的过程，不过实际上我们整个过程中是“在满足条件 X 的前提下处理条件 Y”，这种在计数类问题里会常见一点。
还有一种耦合的办法是，先忽略几个限制，对于一部分限制做完，通过一一调整满足其它限制，这个相比于计数，更适用于找到方案的问题，因为计数的话一般不会知道具体方案，调整起来是麻烦的。
例子是 Lost Cows，这个题我忘了连接了，哪天想起来了补上 [TODO)。
分离变量也可以看作是分别满足的一种，不过我们一般会保证柿子前后相等，就不需要考虑耦合的事情，相当于是简化了问题，比如线段树维护方差，树状数组维护动态矩阵求和问题，或者是一些推柿子题啥的。
考虑换一换考虑问题的角度，比如正难则反。
通过不同的角度重新书写问题，有时候会有奇妙的效果。
比如，我们计算前面的贡献，进行一些决策的时候，如果会影响到后面的某些贡献。
但是决策的顺序似乎又不是那么重要，那么不妨考虑一下倒过来试试。
或者 230923NOIP-T1-qd，如果我们正着做，删除的时候维护最大值是麻烦的，虽然这个题决策的顺序不能变，但是倒过来做也不影响答案，倒过来做就变成了加点的问题，这就好维护多了。
尝试找到问题当中的一些不变量，可以是限制本身，可以是一些其他的东西。
举个例子，大部分插入类问题都可以考虑，是否存在着某种“相对次序”不变的问题。
换句话说我的一次新操作，实际上是不是并不会影响到大部分已有的信息，而只需要计算一些呢？
一个例子是 230414C-T4-ZYB玩字符串。
插入新串之后原有子串的相对次序是不变的，于是可以考虑把一个区间里完整的子串拿掉。计算就方便多了。
当然不只是插入类问题，逆序对啥的也是一样的，交换一次相邻两个元素，对于被交换的这两个元素前后，所能够造成的贡献，实际上是没有变化的。
这个思想看似很蠢，很显然，但在分析形如 AGC054C 这样的问题的时候会很有启发作用。
有很多题的暴力做法都是，类似于状压，需要记录具体的决策情况。
比如说，考虑记 \(dp(u, msk)\) 表示考虑在 \(u\) 的子树当中选了 \(msk\) 这个集合的方案数。
但实际上我们通常可以考虑，“能否只关心决策集合的大小而不关心具体决策是什么”，也就是只关心 \(msk\) 的大小。
一个比较经典的例子是 InfOJ NOIp2023 MOCK T3，不过这个题还需要考虑通过容斥来进行去重。
可能还有很多这样的题，不过我有点记不到了。
贪心策略ψ(｀∇´)ψ
当我们面对一个比较棘手的最优化问题（通常，状态数非常大，枚举起来比较不能接受）的时候。
尝试思考，是否能找到一些，一定不会更劣，一定不会更优的性质，以减小状态数？
不过直接从这个方向出发一般是及其困难的，更好的运用方式是用它来断定某一个贪心策略是否正确。
比如：231023NOIP-T1-Road，这个题如果直接建图枚举，那么复杂度是上了天的 \(O(n^2 + nm)\)，没有前途。
但是注意到每次切换方向都可以走到任何一个路径，所以这里不妨贪心的选尽量小的。
然后可以发现这样一定不劣，于是贪心就是对的。
还有两个类似的题目：230813NanJing-Problem，230927NOIP-Learn。
尝试将多个部分的最优解合并成全局最优解，特别是将限制拆分，再次耦合的时候需要考虑一个问题：
每个部分的最优解是否都是严格限制？或者说，在等价意义下是唯一最优解？
不满足的话，强行将这些部分合并起来，很容易得到错误的答案。
一个例子是：20231113NOIP-Bike，这个题在合并两个生成树的时候，考虑到虽然最小/大生成树不唯一，
但是只要是 mst，它们对答案的贡献实际上是等价的，不会有任何影响，所以我们说，这是在等价意义下的唯一最优解。
那么我们将其耦合起来，一定是等价意义下全局唯一最优解。
小技巧ψ(｀∇´)ψ
关于 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 优化方式
- 230430C-T4-Label 这个题，要通过直接观察 DP 数组本身，找到一大段本质相同的状态，来尝试压缩决策集合以达到优化复杂度的目的。
- 费用提前计算的思想：任务安排，这个可以理解成“懒操作”的反方向，看起来这是决策优化，其实实际上是改变了 dp 状态本身的定义，所以我也将其归类为状态优化。
- 有些题，直接定义的状态状态数太大，没法转移，在一些合适的情况下可以考虑交换值域和答案维，将问题转化为一个判定问题，优化复杂度，比如 230811NanJing-T1-Complexity(AGC033D)，有时也会结合到根号平衡的思想。
对于一个连通性问题来说，dfs 树是一个很有力的工具，我们可以把许多问题拆分到 dfs 树上，用类似 Tarjan 的思想来处理问题：CF19E-Fairy。
树的括号序可以表达的不止有子树关系，还可以表达距离关系（甚至可以带权值）：CF1149C-Tree Generator™
分层图最短路的时候，如果发现连边过多，可以考虑把这些边归类，看能不能新建一层，用一条边来表示：HDU5582-Journey of Taku
基环树相关问题有一个套路，先把树的部分做了，然后考虑合并到环上来做：BZOJ1950-Link，230824CQ-T1-Catch
有一类问题，虽然是区间操作，但是因为多次操作之后会有很多“无用”的操作，此时可以在区间操作中加一个剪枝优化，以达到类似单点改复杂度的效果：区间开根号，维护区间和，区间取模，维护区间 Max，[六省联考 2017] 相逢是问候；
像区间开根号这样的甚至可以使用一个 dsu 维护下一个 1 的位置，以做到更优的复杂度，这个技巧被称作序列并查集。
对于一类对子树整体操作的 dp 问题，设计状态时通常需要考虑子树外的贡献：230626B-T4-Rugby(WIP)
考虑子树外的贡献的时候，因为不知道内外分别有多少贡献，可以考虑钦定贡献再做转移：230829ChongQing-T4-Light
时间复杂度相关
分析复杂度的时候注意形如 \(\sum op_i = k\)，\(cnt \times len = O(n)\) 这样的复杂度。
前者形如有 \(n\) 个段，每个段会有 \(op_i\) 个操作，但它们的总和是 \(O(k)\) 的，于是均摊就是 \(O(k / n)\)，实际复杂度不应当为 \(O(nk)\)。
后者一般出现在一些根号分治题里面，形如可以操作的点有 \(cnt\) 个，看起来级别是 \(O(n)\) 的，但每个操作不会跳到 \(O(n)\) 的复杂度。
前者的例子：231103NOIP-T2-Bamboo。