“没有独自完成的赞歌，没有携手共进的归冢。”
顾名思义，由于一些神奇的原因，我们将一个数据结构维护的每一个点都建立另一个数据结构以达到维护问题答案的操作。一般而言分为外层树和内层树。
外层树一般有线段树和树状数组；
内层树一般有平衡树，线段树和 $\text{Stl}$ 。
树链剖分
其实树剖就是树套树这个思想的前身。因为树剖是树链套数据结构。
其中的外层树就是树链，内层树就是所需要的数据结构。而树套树也就需要这个思想，但外层树不仅仅是树链，而是另一种所需的数据结构。
线段树套 Stl
维护区间前继与修改操作：
写出一种数据结构，可维护以下操作：
- 把第 $i$ 个数修改成 $x$ ；
- 求 $x$ 在区间 $[l,r]$ 内的前继。
对于单点修改和区间查询，我们可以很容易想到线段树，而对前继操作，则考虑 std::set 或者 std::multiset 。
不用担心空间复杂度的条件，因为线段树的性质，std::set 的个数不会超过 $\mathcal O(n\log n)$ （虽然听起来也挺多的了）。
对于操作一，我们可以在原来的 std::set 中删去原数，并添加上 $x$ ，总共会修改 $\mathcal O(\log n)$ 个区间，一次修改的时间复杂度为 $\mathcal O(\log^2 n)$ 。
对于操作二，直接在区间中使用 std::set 中的 lower_bound 或 upper_bound 即可。
P5838
这道题的做法出奇的多，不过总归到底还是一个树链剖分的练习。
正解有什么 $\operatorname{Tarjan}$ ，主席树，智慧法（神仙离线线性算法），分块，莫队等等。
但给一个懒人打法：
树剖套线段树套平衡树（虽然码量大）
首先，用树剖维护路径并对每一条链建立一个线段树，线段树维护 $dfn[]$ 序区间的颜色出现情况，用 std::map 或者 std::set 来维护。
因为本人过菜不会使用 std::set 所以选择了更为费时但简单的 std::map 。
每次查询就 $\operatorname{or}$ 上当前区间的 $Map[c]$ ，当 $res\ne 0$ 时直接判断 $\text{true}$ 。
但总之，$\operatorname{Stl}$ 的存在就已经证明了这个 $\mathcal O(n\log^3 n)$ 的方法不可过，所以直接吸氧，然后解决。现在大部分的比赛都会自带 $\operatorname{O_2}$ 优化，所以不必过于担心。
AC Code
1 |
|
线段树套平衡树
其实 std::set 本身就是一个平衡树，只是这个平衡树已经封装好了，不需要你自己来实现。而现在，我们需要根据题目定义自己实现平衡树。
二逼平衡树
二逼平衡树板子。简化一下题意：
- 询问区间 $k$ 排名；
- 询问区间排名 $k$ ；
- 单点修改；
- 查询区间前驱；
- 查询区间后驱。
除去区间之外，都是平衡树常见的操作，所以考虑外部线段树，内部平衡树。
最慢的操作达到 $\mathcal O(\log^3 n)$ ，所以整个问题的时间复杂度为 $\mathcal O(m\log ^3 n)$ 。
另话：洛谷里这道题似乎非常卡常，离大谱。（调个线段树套 $\text{Splay}$ 调的人心态爆炸，结果最后因为没去 freopen ？？？）还是开了 $\mathcal O_2$ 才过的。
码风指导：封装加 $\text{Splay}$ 。（有时间再写个线段树套 $\text{Treap}$ ）
AC Code Splay ver.
1 |
|
分块套树状数组
这个代码似乎相对而言比较简短，容易实现。
可以用于二维平面中的矩阵区域的点数查询与修改。
例子一
给出 $n$ 个二维平面的点 $(x_i,y_i)$ ，实现操作：
- $opt,a,b,c,d$ ，询问左上角为 $(a,b)$ ，右下角为 $(c,d)$ 的矩阵区域内的点的个数。
- $opt,x,y$ ，把横坐标为 $x$ 的点的纵坐标改为 $y$ 。
强制在线，保证 $x_i\ne x_j(1\le i,j\le n,i\ne j)$ ，$1\le i\le n,1\le x_i,y_i\le n,1\le n\le 10^5$ 。
因为一个 $x$ 只对应一个 $y$ ，所以用一个数组记录这个映射关系，令 $Y[i]$ 表示横坐标为 $i$ 的纵坐标。
以 $\sqrt n$ 分块横坐标，为每一个块建立权值树状数组，记 $Tre[i]$ 为第 $i$ 个块的树状数组，则 $Tre[i][j]$ 表示块 $i$ 里纵坐标在 $\displaystyle\left(j-\operatorname{lowbit}(j),j\right]$ 内点的个数。
这是一个区间带修改的二维偏序问题（至于偏序，之后有机会再写），根据矩阵容斥，可以知道：
$[a,b,c,d]=[1,1,c,d]-[1,1,a,d]-[1,1,b,c]+[1,1,a,b]$
查询
首先暴力处理左右的非完整块区间，统计答案；然后对于完整的块，暴力扫描该块之前的所有块中 $Tre[i][b]$ 的值，即查询 $Tre$ 的前缀和，可以进行性质技巧优化。
修改
可以直接找到 $x$ 所在的块，然后 $add(y_1,1),add(y_2,-1)$ ，并赋值 $Y[x]=y$ 。
对上述操作进行优化，可以视为删点和加点。
空间复杂度
分块 $\mathcal O(\sqrt n)$ ，树状数组 $\mathcal O(n)$ ，总共 $\mathcal O(n\sqrt n)$ 。
时间复杂度
遍历非完整块段 $\mathcal O(\sqrt n)$ ，遍历完整块段 $\mathcal O(\log\sqrt n)$ ，完整块的树状数组查询 $\mathcal O(\log n)$ ，时间复杂度 $\mathcal O(\sqrt n+\log(n+\sqrt n))$ 。
补充
感谢 $\text{@reveal}$ 提供的代码，让我有了一些深入的理解。
这是在线带修二维偏序吧。
对序列分块，值域建树状数组就好了啊。
假设用朴素的方式，大概流程：
- 读入
- 对序列进行分块
- 扫描每一个块，按值域大小建立树状数组
- 将每一个块内的数字放入对应的树状数组
修改：
- 将原来的数字从树状数组中删除
- 将新的数字加入树状数组
查询：
- 扫描散块，统计
- 扫描整块，在树状数组上查找区间和（即某个值域的数字总数）
然后对于非朴素的方式，注意到复杂度并不均匀，查询时扫描整块并查询为复杂度瓶颈。
注意到这具有前缀和形式，即可以通过统计前若干块整块的答案来得到答案。
那么我们可以在修改时，对于对应点之后的整块做修改（类似于树状数组的形式），之后的查询也同样处理即可。
Example Code @reveal ver.
1 |
|
Example Code Eternity's ver.
1 |
|
CF1093E Intersection of Permutations
乍一看，是一个不可做题。实际上，它确实是个不可做题。
我们要查找 $b$ 数组在 $[l_b,r_b]$ 区间在 $a$ 数组的 $[l_a,r_a]$ 区间的映射。
因为 $a,b$ 都是 $n$ 的全排列，所以可以考虑 $\operatorname{Hash}$ 。
用 $Xa[i]$ 表示 $i$ 在 $a$ 中的编号，用 $Xb[i]$ 表示 $b$ 中的第 $i$ 个数在 $a$ 中的编号；构造平面直角坐标系，然后描点 $(Xa[i],Xb[i])$ ，我们就会发现，实际上的询问就是 $[l_a,l_b]$ 到 $[r_a,r_b]$ 中点的个数，然后就可以转换为上一道题。
后面的模板其实都没什么太大难度。主要是上述映射的理解和实现，非常繁琐（我想了一上午都不太清楚怎么实现）
然后直接一波拿下 $\text{11.03s}$ 的最优解第一名。
AC Code
1 |
|