xiaoyaowudi's blog数据结构
链上数据结构
线段树
一般对于每个节点维护区间信息和区间标记。
其中标记需要为一个半群，即满足结合律，例如 $\left(\max,+\right),\left(\min,*\right)$ 上的矩阵。可持久化的标记需要满足交换律。
常用技巧
利用线段树本身结构性质
例：「CEOI2019」动态直径
有一颗 $n$ 个节点的树，边有边权，非负，$q$ 次修改单点边权，询问直径，强制在线
$n,q\le 10^5$
我们考虑维护 $dfn$ 序上的线段树，每个点维护当前这个区间的直径和直径端点，由于边权非负我们可以直接合并两个子区间的信息。
每次修改边权时，假设端点中深度较浅的点是 $u$，对应的区间是 $\left[l,r\right]$ ，那么这个边权只会影响同时与 $\left[1,n\right]$ 和 $\left[l,r\right]$ 交的区间的信息，放到线段树上每层只有 $\mathcal{O}\left(1\right)$ 个点。同时 $\mathcal{O}\left(1\right)$ 求 $LCA$ ，时间复杂度 $\mathcal{O}\left(n\log_2n\right)$
例：GYM103260K Rectangle Painting
一个方阵，初始全白，修改操作每次把一个第 $y_i$ 行第 $l_i$ 到第 $r_i$ 个格子染黑，询问操作每次询问第 $l_i$ 列到第 $r_i$ 列最多有多少个从第 $0$ 行开始的连续黑格子
$n,l_i,r_i,y_i\le 10^5,q\le 10^5$ 强制在线
考虑一个第 $y_i$ 行的白格子对这一列的影响，即使答案对 $y_i-1$ 取 $\min$ ，考虑线段树每个节点开一个 $set$ 维护当前的标记集合，一开始对线段树的根节点打上 $0\sim \max y_i$ 的标记。
每次染黑相当于删除一个区间的标记。删除一个未被染黑的区间时，从跟节点开始，如果当前询问区间完全覆盖当前节点，那么直接从标记集合里删掉此标记。
否则，如果当前标记集合里有此标记的话，就对此标记进行 $pushdown$ 。因为每次都删一个未被染黑的节点，因此需要删掉的节点的标记一定没有被 $pushdown$ 过，即一定存在。
由于询问不保证未被染黑，对每个颜色维护当前是白色的连续段，颜色段均摊即可。
线段树合并与分裂
在树上 $dp$ 时，如果每个点对应的状态数是 $\mathcal{O}\left(n\right)$ 的，且 $f_{u,i}$的转移都只和 $f_{v,i}$ 或$f_{v,1}\sim f_{v,i}$ 有关，那么可以考虑线段树合并
线段树合并的复杂度：假设点数总和是 $m$ ，那么每次递归时会减少一个点，因此复杂度是 $\mathcal{O}\left(m\right)$
由上我们可以知道，区间修改和单点修改的线段树合并都是一个 $\log$ 的
例：维护序列，每次排序一个子区间，单点求值
考虑用 $set$ 维护排好序的连续段，每次相当于合并一些排好序的区间，分裂 $\mathcal{O}\left(1\right)$ 个排好序的区间，线段树合并 + 线段树合并即可，颜色段均摊保证复杂度
通过势能函数维护特殊区间操作
例：维护序列，区间对 $x$ 取 $\min$ ，区间求和 $n,q\le 10^6,x\le 10^9$
吉司机线段树：定义一个区间的势能函数 $\Phi\left(l,r\right)=\left|\left\{a_i\mid l\le i \le r\right\}\right|$ ，即区间不同的数的个数，并维护每个区间的最大值和次大值以及最大值的个数，当 $x$ 大于当前区间的次大值时直接打标记并返回，否则暴力递归处理，这时 $\Phi^{\prime}\left(l,r\right)\le \Phi\left(l,r\right)-1$ ，所以总复杂度为 $\mathcal{O}\left(n\log_2n+q\log_2n\right)$
例：CF1572F Stations
有 $n$ 个广播站，第 $i$ 个广播站高度为 $h_i$ ，范围为 $w_i$。初始 $h_i=0,w_i=i$。广播站 $i$ 能向广播站 $j$ 传递消息，当前仅当 $i\le j\le w$，且 $h_i>\max\limits_{k=i+1}^jh_k$。定义 $b_i$ 表示能向 $i$ 传播消息的广播站数量。
接下来有 $q$ 次操作，分为以下两种类型：
- 给出 $i,g$，把 $h_i$ 变成所有广播站中严格最高的，并且 $w_i\leftarrow g$。
- 给出 $l,r$，查询 $\sum_{i=1}^{r}b_i$。
$1\le n,q\le 2\times 10^5$
首先观察到每个点能广播的是一段区间，每次操作相当于是对左边的点能广播到的地方取 $\min$ ，对右边的取 $\max$，因此考虑吉司机线段树，每次将最大值集体减小的过程相当于是对 $b_i$ 区间加，再拿个树状数组维护即可
例： 「雅礼集训 2017 Day1」市场
维护序列，支持求区间最值，区间和，且支持区间加，区间除法下取整。$n,q\le 10^5,\left|a_i\right|\le 10^9$
定义一个区间的势能函数 $\Phi\left(l,r\right)=\max\limits_{l\le i \le r}a_i-\min\limits_{l\le i\le r}a_i$ ，那么对于线段树上一个节点 $\left[l,r\right]$，当 $\Phi\left(l,r\right)\le1$ 时区间除法下取整操作就变成了区间加法或区间赋值，否则直接递归处理，那么此时 $\Phi^{\prime}\left(l,r\right)\le \dfrac{\Phi\left(l,r\right)+1}{2}$ 。
于是在一个区间的势能函数变成 $0$ 之前至多被访问 $\mathcal{O}\left(\log_2V\right)$ 次，而每次线段树的操作还需额外访问 $\mathcal{O}\left(\log_2n\right)$ 个节点，所以总复杂度 $\mathcal{O}\left(n\log_2V+q\log_2n\right)$
例：UOJ228 简单数据结构练习题
维护序列，支持求区间和，且支持区间加，区间开跟下取整。$n,q\le 10^5,\left|a_i\right|\le 10^9$
同理定义势能函数为极差，那么 $\Phi\left(l,r\right)\le 1$ 时同样为区间加法和区间赋值，而 $\Phi\left(l,r\right)\le 1$ 之前会被访问 $\log\log V$ 次，所以总复杂度 $\mathcal{O}\left(n\log\log V+q\log_2n\right)$
一道和势能函数关系没那么大但是想法类似的题目：
例：[Ynoi2007] rgxsxrs
维护序列，支持求区间最值，区间和，且支持对于一个区间中 $> x$ 的数 $-x$ 。$n,q\le 5\times 10^5,\left|a_i\right|\le 10^9$
注意到对于一个数 $a_i$ ，若 $x< a_i\le 2x$，则操作完后 $a_i^{\prime}\le \dfrac{a_i}{2}$ ，因此我们很容易联想到按值域二进制分组，$\left[2^i,2^{i+1}\right)$ 一组。
定义一个节点势能函数为它所在块的编号，那么一个节点被特殊处理一次势能函数 $-1$ ，所以总复杂度 $\mathcal{O}\left(\left(n+q\right)\log_2n\log_2V\right)$，还需要一些奇技淫巧卡常
一些小技巧
一个从 wygz 博客里学来的东西，如果一个点每次向一个区间连边，支持增删点，然后做并查集的话，可以在线段树节点上记录标记，合并标记时直接将标记所对应的连通块合并即可，打标记时还需判断区间内是否还有点
平衡树
当维护连续段，区间平移，区间翻转时常用平衡树
例：USACO2022.Feb Platinum Painting Rectangles
给定一些没有两条边共线的矩形，将所有区域二染色，求两种颜色的区域各有多少块。$n\le 10^5$
考虑扫描线，维护当前序列上每个点当前所属区域的编号，每次合并时判断两侧是否属于同一个区域即可。
每次遇到一条边相当于区间取反并重标号，标号设置为等差数列即可
关于 fhq_treap 的几件事情
- 树和树之间可以任意合并，只需保证区间无交
- 由于树高保证 $\log$，因此查询时可以暴力跳父亲 $pushdown$
分块
分块的本质是，对于一些容易全局处理的问题，把问题变成 $\mathcal{O}\left(\frac{n}{B}\right)$ 个全局修改操作全局询问操作和 $\mathcal{O}\left(B\right)$ 个单点修改操作 $+\mathcal{O}\left(1\right)$ 个整块重构
例：Yuezheng Ling and Dynamic Tree
给定序列 $a_i$ 满足 $1\le a_i\lt i,\forall 1\lt i\le n$ ，支持两种操作
- $\forall l\le j\le r,a_i\leftarrow \max\left(a_i-x,1\right)$
- 构造一棵树，使得 $i$ 的父节点是 $a_i$ ，求这颗树上 $u,v$ 的 $\operatorname{LCA}$
$n,q\le 10^5$
注意到 $1$ 操作变多后一个节点的深度会变得很小。考虑分块，假设块大小为 $B$
对于块内每个点维护其父链上第一个与其块编号不相同的点。
如果块内的每个点的父亲都不是这一块的，那么直接打加法 $tag$ 即可
否则暴力重构这一块。询问时，暴力跳查询即可。
由于 $1$ 操作至多操作 $B$ 次后就不会有父亲和儿子在同一块了，所以总复杂度 $\mathcal{O}\left(\frac{qn}{B}+qB+nB\right)$，$B$ 取 $\sqrt{n}$ 时达到下界 $\mathcal{O}\left(\left(n+q\right)\sqrt{n}\right)$
分块还可以利用一个性质，所有的标记总数是 $\mathcal{O}\left(n\sqrt{n}\right)$ 的，散块和整块都是，所以两种标记可快速合并的话就可以很方便处理了
例：完美的队列
有 $n$ 个队列，每个队列有一个长度限制 $a_i$，长度超过后会直接 $pop$ 队首。有 $m$ 次操作，每次对一个区间内的所有队列插入一个数，并查询全局所有队列内不同的值的个数。不强制在线。$n,a_i,m\le 10^5$
直接做显然没有数据结构可以维护。
先将操作离线下来，我们考虑对于每种操作求出它加入的那个数第一次在任意一个队列里都不出现的时间，即这个操作修改“失效”的时间，那么从前到后扫一遍即可得出答案。假设这个值为 $e_i$
我们考虑什么东西比较容易维护。
当操作只有全局操作时，显然 $e_i$ 关于 $i$ 单调，可以双指针操作。因此将原序列分块，将操作变成对若干个整块和若干个散点修改
对每个整块和散点维护从当前开始，当前队列里的所有数第一次被全 $pop$ 完的时刻。
然后对于每个操作直接取它包含的整块和散点的时刻取 $\max$ 即可得出 $e_i$
直接做显然是不行的，考虑优化。
对于一个整块，我们可以直接使用上面的双指针维护，并维护一个区间 $tag$，当遇到一个不是包含整个块的询问时暴力重构整个块，这部分复杂度 $\dfrac{n}{B}\cdot \mathcal{O}\left(m\right)+\mathcal{O}\left(B\right)\cdot \mathcal{O}\left(m\right)$
对于一个散点，我们只在需要查询这个散点的状态时对这个散点的双指针进行跟新，并只在 以散点状态而不是整块覆盖这个点 的那些修改上跑这个双指针
此时我们需要记录作为散点“父节点”的整块的 以整块状态修改这个块的 更新情况。
因此我们对每一个整块维护它更新次数的前缀和，以及每个前缀和的值第一次出现的时刻
更新散点的复杂度为 $\mathcal{O}\left(B\right)\cdot \mathcal{O}\left(m\right)$
因此总复杂度在 $B=\sqrt{n}$ 时最优，此时复杂度为 $\mathcal{O}\left(m\sqrt{n}\right)$
树上数据结构
子树型
DSU on tree（树上启发式合并）
这个一般用于处理合并大小为 $n,m$ 的集合复杂度跟 $\min\left(n,m\right)$ 有关的问题，且 $n$ 和子树大小有关
例：区间虚树大小
给定一颗 $n$ 个点的树，每次询问编号 $\left[l,r\right]$ 的点构成的虚树大小 $n,q\le 5\times 10^5$
首先把原问题取个反，统计有多少点不在虚树中。
考虑到一个点不在虚树中当前仅当不存它的子树中的两个点使得这两个点同时在子树中，且这两个点属于这个点的不同儿子的子树。
考虑 dsu on tree，对于每个节点，维护一个 set 存储当前子树中所有点的编号
由于要求两个点属于不同子树，那么对于两颗子树 $T_u,T_v$ ，假设 $T_u\le T_v$
那么我们可以钦定 $T_u$ 中的一个点 $t_0$ 作为 $T_u$ 中被区间覆盖的最小编号的点，那么此时的贡献只和 $T_u,T_v$ 中 $t_0$ 的前驱和后继有关。
此时合并复杂度为 $\mathcal{O}\left(\operatorname{size}\left(T_u\right)\log_2\operatorname{size}\left(T_v\right)\right)$
贡献对答案的影响是一个矩形加矩形求和，离线扫描线做即可。由于有 $\mathcal{O}\left(n\log_2n\right)$ 个矩形会产生贡献，所以两部分的复杂度都是 $\mathcal{O}\left(n\log_2^2n\right)$
长链剖分
这个一般用于处理合并大小为 $n,m$ 的集合复杂度跟 $\min\left(n,m\right)$ 有关的问题，且 $n$ 和子树深度有关
Note: 如果 $n$ 和子树大小有关，那么一个点会被合并 $\sqrt{n}$ 次
上面这个结论成立是因为每跳一次轻边会增加一条 $len+1$ 的长链，那么至多往上跳 $\mathcal{O}\left(\sqrt{n}\right)$ 次
对于点 $u,v$，定义 $f\left(u,v\right)=\gcd\left(\operatorname{d}\left(u,\operatorname{LCA}\left(u,v\right)\right),\operatorname{d}\left(v,\operatorname{LCA}\left(u,v\right)\right)\right)$
对于 $\forall 1\le i\lt n$，求有多少对 $u,v$ 满足 $f\left(u,v\right)=i$ ，$n\le 2\times 10^5$
首先进行莫比乌斯反演，求 $g\left(i\right)$ 表示有多少对 $f\left(u,v\right)$ 被 $i$ 整除
考虑根号分治，对于 $\le B$ 的部分 直接 $dp$ ，令 $f_{i,j}$ 表示 $i$ 的子树中到 $i$ 距离为 $j$ 的倍数的个数，直接 $dp$ ，每个点会正向和反向统计 $B$ 次，复杂度 $\mathcal{O}\left(nB\right)$
对于 $\gt B$ 的部分还是考虑 $dp$ ，令 $f_{i,j}$ 表示 $i$ 子树内到 $i$ 距离为 $j$ 的点数。长链剖分，每次合并两条长为 $u,v\left(u\le v\right)$ 的链时，暴力枚举 $i$ 跳两条链进行答案更新
那么合并复杂度 $\sum_{i\gt B}\frac{u}{i}\frac{v}{i}\le u\cdot \frac{n}{B}$ ，复杂度 $\mathcal{O}\left(\frac{n^2}{m}\right)$
平衡一下复杂度 $\mathcal{O}\left(n\sqrt{n}\right)$ ，实现时第一部分要预处理 $i$ 级祖先，精细实现一下。
线并
例：Qtree4
给定一棵树和一个点集，树有边权，可以为负，要求支持两种操作：
- 点集增删一个点
- 询问点集里距离最远的两个点，可以是同一个
数据范围 $n\le 10^5,q\le 2\times 10^5$
考虑 $dp$ 数组 $f_{u,i}$ 表示 $i$ 时刻 $u$ 结点到子树内最深的点集内的点是什么
由于每个点在点集内出现的时间是若干段区间，区间个数总和是 $\mathcal{O}\left(n\right)$ 的
所以考虑将每个点的出现时间标记到每个点的线段树上并标记永久化，线段树每个结点维护三个值
- $max\_ans$ ，表示这个节点的所有合并的历史时刻的答案最大值，即 $dp$ 时子树内的直径最大值
- $tag$ ，表示所有永久化的这个节点上的标记中的最大值，即一个点集在这段时间区间内的最大深度，$dp$ 时子树内的深度最大值
- $pushdown\_tag$ 表示历史时刻中父链上合并过 $tag$ 的最大值，用于下传的标记
每次合并两个节点 $u,v$ 时，把 $u,v$ 的每个节点在另外一棵树中对应的父链信息更新到这个节点上去。
复杂度 $\mathcal{O}\left(n\log_2q\right)$
线并还可以非常方便地表示出子树内所有的点。
给定一颗 $n$ 个点的树，和 $m$ 条路径，一开始有 $m$ 个棋子在每条路径的起点，每次移动一个棋子，直到每个棋子都到达了终点，每个棋子到达终点前只能沿到终点的最短路径移动，要求任意时刻没有两个棋子在同一位置，问是否能达到要求 $n,m\le 1.2\times 10^5$
首先已知，合法当前仅当存在一种方案，使得可以依次移动所有棋子，且移动过程复合题意。
那么考虑先后顺序是否形成环。对于任意两条路径 $i,j$ ，存在边 $i\rightarrow j$ 当且仅当 $start_i\in j$ 或 $end_j\in i$
这里有一种和 ZJOI2019 语言 类似的方法处理路径问题。类似树上差分，在 $u,v$ 处加入路径 $i$ ，在 $\operatorname{LCA}\left(u,v\right)$ 处删除路径 $i$
考虑线段树分别维护出边和入边线段树。直接线并即可，注意路径 $i$ 连边时要避开自己。
复杂度 $\mathcal{O}\left(n\log_2n\right)$ 实测常数巨大，跑不过 $2$ 只 $\log$ 做法。
重链剖分
这一部分的重链剖分可以支持合并大小为 $n$，$m$ 的集合复杂度和 $\max\left(n,m\right)$ 有关
做法即对一条重链再进行分治，那么一个点在向上跳时至多经过 $\mathcal{O}\left(\log_2n\right)$ 条重链，每条被合并 $\mathcal{O}\left(\log_2n\right)$ 次
全局平衡二叉树
考虑像 LCT 一样构造一个二叉树森林，每条重链为一棵树，根指向树上父亲。
对于每条重链，带权取中点作为当前二叉树结点然后递归构造，权为轻儿子子树大小和 $+1$
那么可以使得任意一个点的深度是 $\mathcal{O}\left(\log_2n\right)$ 的
证明：
若一个点 $u$ 在大二叉树上权大小为 $siz$，那么如果 $u$ 和它的父亲 $fa$ 在同一重链上，那么 $u$ 跳到 $fa$ $siz$ 至少翻倍
如果 $u\rightarrow fa$ 是一条轻边，那么 $siz$ 不会变小
由于最后 $siz$ 是 $\mathcal{O}\left(n\right)$ 的轻边是 $\mathcal{O}\left(n\log_2n\right)$ 的
因此总的深度是 $\mathcal{O}\left(\log_2n\right)$ 的
给定 $m$ 棵一样的树 $T$，对于任意 $1\le i<m$，第 $i$ 棵树的点 $u$ 和第 $i+1$ 棵树的点 $u$ 之间有一条 边权为 $a_u$ 的无向边，树有边权。$Q$ 组询问，每次询问两个点（可能在不同树上）之间的最短距离。
$n\le 2\times 10^5,m\le 10^9$
这条路径一定是在第 $x$ 棵树上 $s\rightarrow u$，然后第 $x$ 棵树上的点 $u\rightarrow$ 第 $y$ 棵树上的点 $u$ ，第 $y$ 棵树上 $u\rightarrow t$
若树和树之间的路径不是在同一个点内走完的，则一定可以把较大的那些边变成较小的那些，一定不劣
设 $l=\operatorname{LCA}\left(s,t\right)$
只需查询 $s,t$ 子树及 $l$ 的外子树内的最小值，$s\rightarrow l,t\rightarrow l$ 两条链上的最小值即可
考虑树链剖分，将询问排序以后扔到每条重链上的线段树区间去查询，这部分复杂度 $\mathcal{O}\left(n\log^2 n\right)$
每个点对答案的贡献都是形如 $k\times a_u+dis$ ，考虑维护出每一颗轻子树的凸包，然后合并重链的时候，将轻子树从下到上编号，然后按线段树的方式分治再合并凸包
每合并完一个区间 $\left[l,r\right]$ 时处理当前区间上的所有询问，由于询问是排序过的，凸包也是有序的
所以可以按归并排序的方式合并和回答询问，复杂度是线性的，由于每棵轻子树会在重链上被分治，深度 $\log n$，而轻子树的大小之和为 $\mathcal{O}\left(n\log n\right)$
因此总复杂度为 $\mathcal{O}\left(n\log^2 n\right)$
如果使用全局平衡二叉树，复杂度是 $\mathcal{O}\left(n\log_2n\right)$ 的
链型
重链剖分
重链剖分不同于 dsu on tree，可以使任意两点之间的重链段数为 $\mathcal{O}\left(\log_2n\right)$
此处和上面同理，如果使用全局平衡二叉树就可以使得任意两点间的路径放到二叉树上是 $\mathcal{O}\left(\log_2n\right)$ 个结点。
例：由乃的 OJ
给定一颗 $n$ 个点的树，每个点有一种操作符（按位或，按位与，按位异或）和一个值，给定 $q$ 次询问，问选定一个 $\left[0,k_i\right]$ 中间的数使得最后结果最大，最大是多少
$n,q\le 10^5$，值域 $2^{k},k\le 64$
第一反应是拆位维护，对于每一位，重剖维护 $0,1$ 经过一条链以后会变成什么，询问时贪心每一位，复杂度 $\mathcal{O}\left(\left(n+q\right)k\log_2n\right)\sim \mathcal{O}\left(\left(n+q\right)k\log_2^2n\right)$
但是发现每一维是互不影响的，所以考虑并行计算，处理 $0,2^k-1$ 经过一条链以后会变成什么，复杂度就可以少一个 $k$，复杂度 $\mathcal{O}\left(\left(n+q\right)\log_2n\right)\sim \mathcal{O}\left(\left(n+q\right)\log_2^2n\right)$
静态LCT
给定字符串 $S$，每次询问一个区间内的所有本质不同子串最少需要分成多少组，使得每组内任意两个串有一个是另一个的子串。
$\left|S\right| \le 3\times 10^5$
结论：假设 $i$ 是最小的，使得区间内所有长度为 $i$ 的子串本质不同，那么答案就是 $len-i+1$
考虑将原问题扫描线，将原问题变成单点查询
我们对于每个 $i$ 维护存在两个长度本质相同的串 $\left[p_0-i+1,p_0\right]=\left[p_1-i+1,p_1\right],p_0<p_1$ ，$p_0$ 的最大值
那么查询的时候只要查询 $p_0\lt l$ 的最大 $i$
考虑建出 SAM，每次更新的时候是一条点到根的父链。我们考虑建出 SAM 的 LCT，这样有一个性质，每颗 splay 每个时刻都是上一次被同时更新的，所以再开一个数据结构，每次一整颗 splay 被更新时直接打标记即可。
由于 LCT 的 access 次数为均摊 $\mathcal{O}\left(n\log_2n\right)$ 因此总复杂度 $\mathcal{O}\left(n\log_2^2n\right)$
无根型
点分治/边分治
把树形结构变成菊花状结构，适用于序列分治结构，或钦定根的结构。
例：「LibreOJ Round #11」Misaka Network 与 Accelerator
给定一个树上 2-sat 问题，每个限制是一个树上结点和对于它距离在 $\left[L,R\right]$ 内的所有点。$n\le 5\times 10^4,L,R$ 为定值
考虑直接点分，此时每个限制是对一个距离点分根结点 $\left[l_0,r_0\right]$ 且和 $u$ 不同子树，离线下来前缀后缀建立主席树优化建图即可，复杂度 $\mathcal{O}\left(n\log_2^2n\right)$ ，不太能通过
注意到上面这个做法并没有利用 $L,R$ 是定值的特点，我们考虑每次点分的时候对于深度按 $R-L+1$ 分块，那么每次连边就是一个块的前缀/后缀
这样连边就是 $\mathcal{O}\left(n\log_2n\right)$ 了。
其他
虚树
对于 $k$ 个点构造出的虚树，点数，边数和结点度数总和都是 $\mathcal{O}\left(k\right)$ 的
虚树构造的本质就是不断去掉叶子节点并缩链
给定 $n$ 个点 $m$ 条边的连通图，求独立集个数。$n-1\le m\le n+10$
首先这道题可以用 [UOJ138 开学前的涂鸦]() 的 trick 变成集合幂级数的题。
考虑图的生成树，那么这个图至多有 $11$ 条额外边，
我们发现，树形 $dp$ 唯一的问题是 $dp$ 到 $\left(u,v\right)$ 这条额外边中深度小的那个点时，需要知道 $v$ 的状态
那么我们枚举每条额外边中较前的那个点然后在虚树上 $dp$ 即可
复杂度 $\mathcal{O}\left(n\log_2n+2^{m-n}\left(m-n\right)\right)$
分治
线段树分治
一般对某一维（一般时间）进行分治，把增删操作变成只增或只删，或通过标记永久化把一些可加信息的询问变成全局询问。
例：CTSC2016 时空旅行
有一些时空，每个时空是由父时空增/删一个星球得到的，保证关系形成一棵树，星球坐标是三维的，每次询问一个时空到 $x=k$ 的平面最近的星球
$n,q\le 5\times 10^5$
考虑没有增删，只有全局询问。星球到平面的距离可以表示为 $\left(x-k\right)^2+y^2+z^2=-2kx+\left(y^2+z^2+x^2\right)+k^2$，相当于 $y=-2kx+b$ 去截 $\left(x_i,x_i^2+y_i^2+z_i^2\right)$ 这些点得到的最小截距 $+k^2$，因此可以将所有点的下凸包建出来，所有直线按斜率排序，单调的扫一遍即可。
此时直接线段树分治是 $2\log$ 的，因为每个节点还需要排序，直接排序再插入线段树就是 $\mathcal{O}\left(\left(n+q\right)\log_2\left(n+q\right)\right)$
例：CF576E Painting Edges
有 $k$ 种颜色，定义一个图是合法的，当且仅当保留任何一种颜色边都是合法的，初始每条边无色，每次染色一条边，可以重复染，只有染完是合法的才会染，输出每次操作是否被执行
$n,q,m\le 5\times 10^5,k\le 50$
考虑每种颜色只插入边时怎么做。维护一个并查集，记录每个点的父亲以及到父亲的路径上经过了的边数 $\bmod 2$ 的值。
对每条边的每个两次修改之间的区间分治到线段树上，由于上一次的区间都是在这一次的区间之前被计算，所以后续区间的颜色都可以在计算前被确定
序列分治
序列分治一般处理可快速合并两段连续区间信息，信息不可减的区间问询问题。
例：WC2022 秃子酋长
给定一个长为 $n$ 的排列，$q$ 次询问，每次询问一个区间，求将其排序后相邻两项在原序列中的位置差的绝对值之和，询问独立，$n,q\le 5\times 10^5$
序列分治，然后考虑怎么合并左右区间，对于只考虑右区间时右边相邻的一对点 $\left(i,j\right)$，其对答案的贡献为
- $i+j$ ，当且仅当左区间中存在一个数 $a_k$ 使得 $a_i<a_k< a_j$
- $\left|i-j\right|$ ，当且仅当左区间中不存在这样一个数
考虑贡献为第一种的位置，容易发现这是单调的，即出现位置是左侧区间的一段前缀，那么对于每个 $a_k$ 记录其出现的位置然后取区间最大值即可，然后就是区间加法单点查询。对于右侧区间，从左到右加入点，每次会增删 $\mathcal{O}\left(1\right)$ 个点对，用 $set$ 维护即可，也可以倒过来链表操作。
CDQ 分治
CDQ 分治一般用于解决询问依赖高维偏序的问题，
通过将某一维排序后递归处理，再将另一维归并排序把 $K$ 维偏序转成 $K-1$ 维偏序做。
一般只能处理离线情况，数点问题可以花费 $\mathcal{O}\left(\log_2n\right)$ 的代价降低一维
常用模型
高维数点
- CDQ 静态离线
- 树套数据结构在线动态
- 可持久化数据结构静态在线
有一个 $m\times n$ 的数组 $a_{i,j}$
定义：$\displaystyle f\left(i,j\right)=\min_{k=1}^m\left(a_{k,i}+a_{k,j}\right)+\max_{k=1}^m\left(a_{k,i}+a_{k,j}\right)$
求 $\sum_{i=1}^n\sum_{j=1}^nf\left(i,j\right)$ $n\le 2\times 10^5,m\le 4$
首先将 $\max$ ，$\min$ 分开来算。
考虑第 $k$ 行成为最小值的条件，即 $a_{k,i}+a_{k,j}$ 小于等于其他三行对应的值
那么 $\forall t\neq k$，$a_{t,i}+a_{t,j}\ge a_{k,i}+a_{k,j}$
那么 $a_{k,i}-a_{t,i}\le a_{t,j}-a_{k,j}$
那么钦定一行作为最小值然后三维数点数情况数即可。
复杂度 $\mathcal{O}\left(2mn\log_2^2n\right)$
扫描线
扫描线本质即为将一维区间修改变成 $\mathcal{O}\left(1\right)$ 次区间修改，查询变成前缀查询，维数 $-1$ 。
矩形加正数 矩形查询 $0$ 的个数
扫描线，线段树维护历史最小值及其个数
矩形加 求矩形 $\max$
分治扫描线维护区间历史最大值
其他技巧
平衡复杂度
当修改和询问个数不同级的时候，就可以使用询问修改复杂度不同级的数据结构平衡复杂度
例：区间独特的城市
给定一棵 $n$ 个点的无根树。定义 $v$ 是 $u$ 的独特结点当且仅当：
- $v \neq u$。
- 以 $u$ 为根时，不存在非 $v$ 的结点与 $v$ 深度相同。
作为这棵树的管理员，你需要回答 $q$ 组询问。每组给定区间 $[l,r]$，你要求出满足 $l\le u,v\le r$ 且 $v$ 是 $u$ 的独特结点的有序点对 $(u,v)$ 个数。
$n,q\le 2\times 10^5$
根据独特的城市题解，在找到直径端点后，我们可以在 dfs 过程中维护一个栈，里面是当前点的独特结点。
因此考虑把对栈的操作建树：维护一个当前点，进栈时添加一个叶子把当前点往下移，出栈时让当前点返回父亲。再考虑 $v$ 是 $u$ 的独特结点。那么 $u$ 会对应操作树上某时刻的当前点；$v$ 进栈次数不超过 $\text{deg}(v)$，会对应这么多个无祖先-后代关系的点。独特关系成立当且仅当 $u$ 对应的点在至少一个 $v$ 对应的点的子树里。
所以问题就变成了询问一个区间内的点有多少对祖先-后代关系。直接莫队是 $O(n\sqrt q \log n)$。考虑二次离线，之后只要 $O(n)$ 次单点修改和 $O(n\sqrt q)$ 次区间求和。可以用分块平衡两边的复杂度，做到 $O(n \sqrt q)$。
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。