太困难。
P7124
前置知识：Eden 的新背包问题。
这个题做法比较离谱。题意是求子树补不删除莫队。要求操作次数 \(O(n\log n)\)。
考虑类似于线段树分治的结构，如果递归左儿子，就加入右节点信息；如果递归右儿子，就加入左儿子信息。这样我们能在 \(O(n\log n)\) 次操作种算出每个叶子在序列中代表的位置的补。
放到树上，我们用轻重链剖分把这个树剖成一些链。首先我们考虑重链上的元素如何处理。考虑如果递归到重链顶的时候（钦定此时已经算出以该重链顶为根的子树补），那么对于重链上的每一个点，我们只需要加入其到重链顶路径上的所有点和所有轻儿子。这个东西均摊下来是 \(O(n\log n)\) 的，因为一个点只会加入该点到根路径的轻边个数次，也就是 \(O(\log n)\) 次。
然后我们考虑轻子树怎么整。这个时候我们就能类似于上面 Eden 的新背包那样做了，但是此时轻子树带权，所以我们建出哈夫曼树。
哈夫曼树就是最优的带权二叉树，每向上两层子树大小加倍。其构造方法就是每次选叶节点权值和最小的两棵子树拉出来合并成一棵子树，一直到最后只剩一棵树。
考虑对于每个重链都这么做，分治哈夫曼树同样是 \(O(n\log n)\) 的。接下来就是把哈夫曼树通过轻边连起来，具体就是某重链的哈夫曼树的根和其父亲的叶子相连。易证该树高为 \(O(\log n)\)。直接分治，然后遇到树上节点或重链顶的根就对应操作即可。时间复杂度 \(O(n\log n)\)。
P2325
树分块前置题。定义首都为界点。
考虑自底向上维护一个栈。记录刚遍历到该点的栈的大小。如果要遍历子树的时候栈的大小增量大于等于 \(B\)，那么我们就合并栈内的元素为一块。注意到最后不能只剩一个大小小于 \(B\) 的东西在栈里，所以我们最后把这个东西和我们分出的最后一个连通块合并，就能满足题中所有条件。时间复杂度 \(O(n)\)。
然后 lxl 就给我们普及了一个比传统分讨来分块更好的办法，即 P2325 + 建虚树，每次把虚树上的一条边所对应的连通块找到就能完成每块包含界点最多 \(2\) 的一种分块构造（top cluster，界点为 \(2\) 是为了好打 tag）。但是实际上好像有比这个分块方法更简单的方法（
然后是几个非洛谷题。注意到可能有用的只有一个 trick。考虑如何找到一个节点的祖先子树内第一次包含某种颜色。这个东西就是对每一种颜色建 set（dfn 桶），然后直接求这个东西的 dfn 前驱和该点的 LCA，还有其 dfn 后继和该点的 LCA，取深度更浅的即可。查询或修改的时间复杂度均可以做到 \(O(\log n)\)。
P8204
这个东西是构造有向邻域的不删除莫队。
首先 top cluster 分块。我们有一种比较简洁的方式找到一种 top cluster 分块的界点构造。每次遍历子树，如果子树内所有未分块元素个数大于 \(B\) 或者子树内有超过 \(2\) 个界点，那就在这个地方放个界点。暂时没有想到如何把界点转为完整分块的一种简洁方式，但是这个题只需要界点间的路径就行了。（好像只需要 DFS 一遍只有一个界点的连通块再分一次块就行了/yiw）
记录出现在路径上的询问，不出现在路径上的询问大小都是 \(O(B)\) 的，可以直接处理。
然后对于每个块把路径上的询问全部按深度排序，然后用类似于序列上的回滚莫队做法，先拓展右区间，然后每次查左区间然后直接撤销。这样我们就能和回滚莫队做到一样的询问次数。
P4475
大家都说是 KDT 板子题，但是我不会 KDT。所以我用 lxl 讲的平面分块来做了。（熬到凌晨接近 3 点才过，简直简直。）
对平面分成 \(\sqrt n\times \sqrt n\) 块（边长 \(\frac{M}{\sqrt n}\)，但是注意这个题不是完全随机，\(M\) 可能会变），根据随机，每一块内期望只有 \(O(1)\) 个点，所以我们可以直接暴力查与线有交的 \(O(\sqrt n)\) 个区间，然后维护前缀后缀和即可。时间复杂度 \(O(m\sqrt n)\)。
hpi 我就暂时不写了。
P8529
真的是什么都能出莫队。这个题是半平面莫队。
我们先随机撒 \(B\) 个点，对于每个询问向上平移至最近的一个关键点，那么每个点期望有 \(O(\frac{n}{B})\) 个询问。考虑做一遍旋转扫描线的代价是 \(O(n)\) 的。每次处理跨点的询问也是 \(O(n)\) 的，我们取 \(B=\sqrt n\)，所以我们得到了总代价为 \(O(n\sqrt n)\) 的做法。
中间有一些巨大卡常难写题暂时先不写。
P4198
这个东西有点离谱。就是你考虑到我想了一个单 log 假做法，发现假了之后在其基础上写了双 log，一直 WA。然后重构代码一遍就过了（
这个东西是线段树单侧递归板子。我们考虑直接维护区间答案长度和右子树在左子树的基础上的答案。这个时候我们有左子树的最大斜率，我们想要跑到右子树里面算贡献进行合并。这个时候我们发现维护区间最大斜率，每次合并我们可以直接递归右子树，如果遍历到某点时左子树最大斜率大于传入的最大斜率，那么就累加右子树在左子树基础上的答案，然后递归左子树，反之直接递归右子树就行了。主要是需要保证右子树内有元素的斜率大于左子树内的最大斜率。
每次合并是 \(O(\log n)\) 的，所以每次修改是 \(O(n\log^2 n)\) 的。
CF1340F
单侧递归的一个练习题。考虑我们在线段树上维护一个形如 )}]}{{( 的序列的前半后半的正反哈希值（反着的时候就是倒着哈希，左括号右括号互换）。同样考虑如何合并两个区间。我们一定是去想抵消中间一部分括号，否则这个东西一定不合法。考虑我们
钦定左区间的左括号数量比右区间的右括号数量多（反之其实同理），我们为了检验是否匹配，等同于我们要求一个区间的左括号的后缀哈希值。
这个东西我们发现我们有单侧递归做法：如果后缀长度小于等于右区间贡献的括号长度，我直接递归右区间；如果大于等于，我们发现查询变成一个区间，这样是不行的，而因为这个地方是匹配的，所以我们把区间变成一个后缀减去另外一个后缀的哈希，不难发现另外一个后缀的哈希就等于右区间的右括号反哈希值。这样我们就有 \(O(\log^2 n)\) 的修改方法了。
考虑查询的时候怎么合并哈希。考虑我们用一条虚链把线段树上的那 \(\log n\) 个区间的信息连起来，然后我们发现我们只需要再写一个函数来递归这个结构来看是否匹配就行了，递归查询方式和上面是一样的。树高是 \(O(\log n)\) 的，所以时间复杂度是 \(O(\log ^2 n)\) 的。
同样的，rupq 暂时不写了。
CF414E
这个是 ETT 弱化版题目（lxl：ETT 不在考纲里，但是平衡树维护欧拉序在考纲里，而且不是 10 级）
考虑用平衡树维护欧拉序（即遍历到这个点和从这个点回溯的时候都把这个点加入到序列里）。我们把这个点的加入点和删除点对应在平衡树上的节点编号都记录下来，方便我们找这个节点当前是序列中的排号为多少的点。具体就是维护一个 fa 标记，每次跳父亲统计前面的点个数。
使用 FHQ-Treap（这玩意我好久没写了）。\(1\) 操作就是求区间的深度最小值，除了它们两者有一个是另外一个点的祖先的情况（这个东西可以特判），然后 LCA 的深度就是深度最小值减一，然后利用 \(dis_{u,v}=dep_{u}+dep_{v}-dep_{LCA}\times 2\) 可以轻松求得答案。
\(3\) 操作就是利用深度变化是连续的，即一个区间内如果深度 \(d\) 满足在该区间最小值最大值之间的话，这个区间内一定有点的深度为 \(d\)。我们等于说找到 dfn 序最大的一个深度为 \(d\) 的点。这个东西是容易的，具体就是如果右子树的最小最大值满足条件就直接递归右子树，然后再看该节点的深度是否为 \(d\)，最后再递归左子树。
剩下一个 \(2\) 操作。这个东西其实就是一个区间平移，然后区间修改 dep。然后我们用 \(3\) 操作的办法找到询问点的 \(h\) 级父亲（区间 \([1,in_{u}]\) 之中的最后遍历到的深度为 \(dep_{u}-h\)）的点。然后操作中要求的 最后一个儿子 就是把这个区间平移到 \(out_{u}\) 前面就行了。
P5354
考虑维护函数复合。拆位，然后再把拆的位压回去，容易有 \(O(1)\) 合并标记的方法。然后按位贪心就行了。