lxl 学长讲课笔记
常数种可能性的状态
通过预先处理多种状态的信息，从而快速的转换状态。
经典操作：flip。
分析信息的思路
- 利用线段树
利用线段树的时候，如何合并两个分支区间的信息，我们需要有如下注意：
-
答案 - 依赖的信息，继续的依赖，这样就能找到需要维护的东西。这终会产生闭包。
-
合并时，我们只需要考虑跨过分治区间对于答案的贡献，对于不同的情况进行讨论即可。
只是在这里，两个分治区间的信息可以快速地合并罢了。
- 对于不独立信息的处理
独立的信息指区间 \(\max\) 区间和问题。
不独立的如配对相关问题，经典的有前驱后继，或者 \(a_i + a_j = w\) 的问题。
一种做法是离线进行扫描线，但是不能带修，一种是强行进行高位扫描线，也就是莫队，可以带修，但是复杂度可能无法接受。
然而更好的做法我们需要尝试将不独立的信息变的独立：
-
配对问题中合理的利用
pre会有奇效！ -
配对问题可能出现 \(O(n)\) 影响
pre的情况，我们需要合理利用支配的性质来减少不必要的影响。
例如 P6617 查找 Search 中有很好的体现。
- 在什么地方使用数据结构？
一般来说，我们有两种方案：
- 对于信息建立数据结构，在询问时对其进行查询。
- 对于询问建立数据结构，利用信息更新最终答案。
在 CF702F T-Shirts 中有很好的体现，这两种思路都可以。
小技巧
颜色段均摊
对于 ODT 来说，其区间推平的复杂度是 \(O((n + m) \log n)\) 的，十分的优秀，但是对于查询来说，我们需要通过分块或者线段进行辅助，从而达到正确的复杂度。
判断是否可以均摊，我们可以看是否能够构造出一个操作序列使得序列复原，如果可以复原，那么基本是不可以均摊的。
或者我们看是否能找到一个量，不增，或者不减，或者有一个神秘的上界。
更详细的文章：# 算法学习笔记(42): 颜色段均摊
容均摊
对于 \(\sqrt x\) 的操作，可能可以通过 \(\max - \min\) 的势能来搞定。
如果发现极差会变化：\(\max - \min \ne \sqrt{\max} - \sqrt {\min}\)，那么便可以暴力递归下去修改，否则可以整体打一个 \(\sqrt x\) 的标记。对于区间加减，在线段树上至多影响 \(O(\log n)\) 个节点的势能，所以复杂度并不会有问题。
类似的操作有 \(\lfloor \frac x d \rfloor\)，这可以将除法操作变为对于区间的加减操作。