Summary scoi/noip ds

1. 吉司机线段树

平常我们的线段树处理问题的时候，其实已经有体现这样的思想：如果当前区间是全部都被影响的，那么打上tag返回，如果是全都没有被影响的，那么直接返回，如果是一部分被影响的，直接暴力向下递归直到前两个条件满足。但是这种处理方式适用于影响的数一定都是一整段的，那么如果像取 min/max 这样的话，其实它就相当于是区间中部分数进行推平赋值的操作，所以要想使用线段树进行操作，就同样必须找到怎么把要操作的数单独剥离出来的方法，这时候，我们就改为通过只对 max/min 值进行操作来进行维护，其实上，这种方法就是：如果条件弱的时候不好维护（很难打tag来更新），那么就暴力，等到条件强的时候再来维护。

那么，我们就解决了这种新的操作，但是其实还有两个重点就是：a) 区间最值操作和其他操作的复合 b) 区间历史信息。 要处理这样的信息，我们就要认识到打lazytag的本质就是保存压缩的操作序列，我们前面的转化操作就是在确定这个操作序列施加的对象（无论对于普通线段树还是吉司机），注意顺序即可。

现在来看历史最值，大多数问题，都可以直接利用lazytag，只需要对不同的操作类型分别维护最大的修改操作。其实对于修改的操作 +/history_max ，这两个运算之间的关系与+/* 很类似，可以用矩阵来描述这些修改（还记得“连分数”？其实矩阵是可以很好描述操作序列的），然后也可以通过在线段树上维护矩阵标记（其实是一样的）

然后如果同时要维护什么区间最值和历史最值还有其他操作呢？可以直接拆成最大值和非最大值进行处理，拆完就变成跟没有区间最值一样的了，这就是吉司机线段树处理数域的思想加上矩阵的思想，如果再分析，把矩阵精简，把乘法展开，就直接得到了那些复杂的标记下传，emm。至于如果要同时支持求和操作，那么直接再维护一个sum就可以了。

线性代数改变世界！

2. 线段树合并/分裂

通常这种方法都是要综合线段树上二分等一起使用的，本来利用线段树的结构，就可以快速解决某些问题，比如求逆序对。

但是注意线段树合并的复杂度有可能不对。

这边有一个Trick，就是我们可以把暂时没有用到的部分全都合成一个点，然后用到的时候再分裂，或者是分裂和合并整到一起（TJOI2016排序），这时候一般都要利用线段树的结构特征，维护一些不寻常的信息：

• 下标有序（权值线段树）

• 可以进行线段树上二分

3. 可持久化权值线段树

以下简称主席树

可持久化权值线段树是一种前缀和形式的线段树结构，因此，除了它基本的回溯历史的作用，还可以主席树上差分（静态区间第k小）

Trick 标记永久化：如果维护的信息对时序没什么要求（交换律或由于某种性质能够确定时序，例如 TET-3D），就可以使用标记永久化。

4. 树链剖分

树链剖分把树按照某种规则剖分成 \(\mathcal O(\log n)\) 条链，配合 DFN 序将链平铺到序列上，可以使用数据结构来进行维护。哦这只是重链剖分，他的原则是：一条重链尽量往大小大的儿子延展。由于我们后面要用数据结构维护，我们就要尽量少切换链，由于我们这种大小平衡的思想（其实想想和什么启发式分裂还是有点像），每切换一次链（付出一次代价），子树大小都减少一半，这就意味着不可能切换太多次。

这一点甚至比整个树链剖分重要得多，就是这种用大小进行限制的思路（启发式合并/根号分治/按秩合并），就是大的东西通常意味着大的代价，而由于总量有限，大的不会多，小的不会大，在遇到一些决策的时候，考虑集合按大小划分有时候能带来很大的效果。

5. 可持久化平衡树

啊，就是可持久化的平衡树啊

但是请记住fhq每次分裂都会新建，所以这是有几倍的空间常数的。

若干序列上基本问题

1. 偏序问题

1. 1维偏序

   就是排序

2. 2维偏序

   即逆序对

   • 静态全局逆序对

     1. 树状数组扫描 \(\mathcal O(n\log n)\)

     2. 归并排序 \(\mathcal O(n\log n)\) ，等价于 CDQ 分治 （分治时只让左边贡献右边保证了第一维，里面排序保证第二维）

   • 静态区间逆序对

     【离线】莫队二次离线，\(\mathcal O(n\sqrt m \log n)\)

   • 动态全局逆序对

     1. 【离线】CDQ分治（加上一个时间的维度，只对某些修改可用）

     2. 【在线】树状数组套权值线段树

3. 3维偏序

   有的时候第三维是一个时间维，你要自己加上去

   • 先排序再CDQ再树状数组

     排序再CDQ解决了第一维限制，中间再排序解决第二维度限制，然后再树状数组解决第三维限制

   • 排序之后CDQ套CDQ

     第一次CDQ解决第一维，然后排序第二维之后再标记一下哪些是从第一层左边来的哪些是右边来的，第二次CDQ的分治解决第二维的限制，再对第三维排序，同时只允许第一层左边来且在第二次也在左边且第三维排序之后满足条件的进行贡献。

   • KDT

   • 先排序然后树套树

4. 更高维度偏序

   别想了，KDT启动！CDQ再套就太慢了

Trick 这些问题通常可以转换为偏序：

• 很明显的条件限制

• 树上的深度限制（有些时候也用线段树合并）

• 树上的子树限制（dfn）

2. K-th 问题

1. 静态全局kth

   排序啊

2. 动态全局kth

   【在线】平衡树/线段树二分

3. 静态区间kth

   【在线】主席树

   【离线】莫队+值域分块

   【离线】整体二分

4. 动态区间kth

   【在线】树状数组套权值线段树

6. LCT 动态树

它来了它来了

LCT 在把一棵树分成若干实链，为了快速跳实链以及维护链上信息，选择了Splay这种方便进行换根的数据结构，它结构很灵活，可以支持快速切换链的虚实状态。所有对于链的操作全部都可以转换成对 Splay 的操作。

Trick 维护子树信息：由于动态树进行操作的时候，都是对选出的实链的操作，所以要维护这些子树信息就要考虑区分实儿子和虚儿子的信息，否则在换root、断边等虚实儿子切换的时候就不能维护了。如果信息没有可减去性，可以考虑再在节点上维护一个数据结构。

若干树上基本问题

Trick 树链剖分的dfn序同时包含子树的信息和链的信息，一些难以维护的（比如颜色数量）信息，可以使用这种dfn序然后进行树上莫队，但是在处理子树信息的时候注意LCA处的特殊处理。

Trick 树上主席树：以父节点为基础版本向子节点延展，可以在一个 log 的时间里解决静态路径第 k 小问题。

Trick 在线莫队？（为什么在这里） 当在线的时候，无法从上一个答案区间转移，则可以选取若干点（每隔 \(\sqrt n\) 选择一个），然后预处理这若干点中间的答案，询问时选择最近的区间转移而来，如果要支持修改，那么可以在每次修改的时候修改莫队里面维护的信息（就比如数颜色中维护的彩笔序列），然后记录每一个关键区间的更新时间，在查询的时候如果用到的区间过时则直接重算这个区间进行更新。

Trick 树上前缀和：可以以父节点的版本转移到子节点的版本，如果这种信息能够支持取出深度更大的版本（就比如时间戳线性基）那么就可以快速支持路径查询（消耗一次合并代价）

Trick 树上ST表：凡是重叠区间的重叠部分不会重复贡献的信息（就比如线性基、gcd、max）那么可以倍增预处理这样的信息，然后查询的时候像ST表一样，可以快速支持路径查询（消耗1次合并代价）。

把序列上的数据结构转移到树上，可以用树链剖分，也可以按照这种深度的方式转化，因为树也是一种只有一个前驱的结构，所以前缀和、倍增是可以适用的。

7. 圆方树

现在想来，对于仙人掌来说，vDCC的性质是要好得多的，因为，仙人掌上的vDCC一定是一个简单环，然鹅eDCC就有可能不是简单环，就比如我之前放的这张图片。

上面是按vDCC，下面是按eDCC。

所以实际上如果是一般无向图，那么大概率就是要维护和割点割边有关的东西，比如路径上割点（无向图必经点），然后转换之后可以变成树上信息维护。

8. 左偏树

二叉堆虽然保证了深度，但是这也导致结构必须要是完全二叉树，很难支持合并，于是我们借助跟FHQ差不多的思想进行合并，通过一个左偏性质找到最近的可合并的位置

我们可以采用并查集来维护堆顶。

Trick 启发式标记下传：要合并堆的时候，如果要维护堆顶的标记，则直接暴力下传较小的堆顶的标记

Trick 启发式分裂：有时候要处理一些点对的数量，跟一段区间内的最小值或者最大值有关系，对于每一段区间 \([l,r]\) 找到最值之后以该位置划分，枚举较短那段的点查找另一边的配对数量（配合其他数据结构），然后再对左边右边做这样的操作。这种通过分治横跨来确定贡献的思路很常用。