( ext{[ONTAK 2010] Peaks})

解法

首先可以想到是 ( m Kruskal) 重构树，问题转化为求重构树中某子树的第 (k) 大权值。

先开始想写线段树合并，后来发现要写可持久化，不然由于中间的版本将地址给了后面的版本，就不能查询中间版本了。

其实这题也可以用 ( m dfs) 序解决，将子树转化成序列问题。对于本来就有的点，加入自己；对于每个重构树新增的点，记录 (st,ed)，最后查询这个区间中的答案即可。

代码

( ext{Link.})

训练士兵

解法

将询问和修改差分。令修改 ((x,y,w)) 表示将横纵坐标都分别大于 (x,y) 的点都加上 (w)。这样我们需要考虑 ((x,y,w)) 对 ([1,1]-[i,j]) 的贡献

[ ext{Ans}=sum_{x=1}^isum_{y=1}^j (i-x+1)cdot (j-y+1)cdot w_{x,y} ]

[=(i+1)(j+1)cdot sum_{x=1}^isum_{y=1}^j w_{x,y}-(j+1)cdot sum_{x=1}^isum_{y=1}^j xcdot w_{x,y}-(i+1)cdot sum_{x=1}^isum_{y=1}^j ycdot w_{x,y}+sum_{x=1}^isum_{y=1}^j xycdot w_{x,y} ]

所以只需要维护四个变量即可。

由于是先修改再查询，我们可以不使用树套树，而是将 (x,y) 坐标离散化后，以 (x) 坐标为主席树的根，将 (y) 在主席树上维护。查询也是 (mathcal O(qlog n)) 的。

代码

( ext{Link.})

( ext{Couple Trees})

题目描述

给定两棵大小均为 (n) 的树，它们共用相同的节点。保证 父亲的编号一定比儿子小。

有 (m) 个询问，每个询问为 ((x,y))，询问从树 (1) 的 (x)，树 (2) 的 (y) 开始向上走，能走到相同 ( m id) 的最深的点。你需要输出这个点以及 (x,y) 到这个点的步数。

解法

可以先将树 (1) 来一个树剖，这样 (x) 到根的路径可以被表示成几段区间。对树 (2) 做主席树，儿子继承父亲的版本，在树 (1) 的 ( ext{dfn}_x) 的地方插入 (x)。这样对于查询，我们可以在第 (y) 个版本的主席树中查询 (x) 到根路径被表示的区间，这是 (mathcal O(qlog^2 n)) 的。

( ext{JZOJ - 4616}) 二进制的世界

题目描述

给定长为 (n) 的序列 (a)，你需要对于每个 (iin[2,n])，求出 (a_i ext{ opt }a_j) 的最大值，其中 (jin[1,i))，( ext{opt}in { ext{or,and,xor}})。

(nle 10^5,0le a_i<65536)。

解法

最朴素的暴力是记录数 (x) 是否出现过，(mathcal O(1)) 插入，(mathcal O(2^{16})) 询问。

我们可以增大插入时间，减少询问时间。令 (f_{i,j}) 为前 (8) 位为 (i)，后 (8) 位为 (j) 的数进行运算 后 (8) 位 的最大值（这里其实前/后没啥区别）。那么假设插入的数前后 (8) 位分别为 (x,y)，就有

[f_{x,j}=max{f_{x,j},j ext{ opt }y} ]

假设询问的数字前后 (8) 位分别为 (x,y)，就有

[ ext{Ans}=maxig {f_{i,y}+(i ext{ opt }x)cdot 2^8ig } ]

( ext{K })个串

解法

题目是比较经典的堆的问题，因为 (kle 2cdot 10^5)，我们可以以 (iin[1,n]) 作为右端点，先将右端点为 (i) 的最大子串塞进堆，取出堆顶，发现最大子串将左端点区间分成两段，在两段中各取最大值即可。

问题是如何快速维护右端点为 (i)，左端点在某一区间的最大子串。可以考虑以右端点为根建立主席树，左端点对应着树内下标。这样每次右移右端点 (i)，它的贡献就是在 ((lst_{a_i},i]) 中加上 (a_i)。

实现上为了控制内存，写了个标记永久化（这样每次还是增加大概 (log n) 个点），记录一下几个小 ( m bug)：

在 ins() 函数中，我们不能将 ( m lazy) 标记写成函数的递归传递，每次加上这个节点的 ( m lazy)。因为在修改的时候，这个节点 (o) 的儿子可能不被修改覆盖，这个儿子就没有加上 ( m lazy) 标记，更新 (o) 就会出错。最好的写法是修改时不将标记下传，在 pushUp() 时加上标记即可。这样后面 ask() 也更好办一点。
每次修改区间之后，不能直接将 (rt_i) 的最大值塞进堆。这也是写法的问题，因为 (rt_i) 是 ([1,n]) 的最大值，而 ([i+1,n]) 初始是 (0)，如果 ([1,i]) 区间内的数都 (<0) 就会出错。

代码

( ext{Link.})

( ext{BZOJ - 4771 })七彩树

解法

树套树？似乎也不好处理颜色。题解的做法是以深度建立主席树，维护树上 ( ext{dfs}) 序。插入时将节点按深度排序。假设处理到 (x)，那么 (x) 对到根的一条链都贡献 (1)，找到与其同色且先插入的点中的前驱 (pre) 与后继 (nxt)，那么 ( ext{lca}(pre,x), ext{lca}(nst,x)) 的贡献就 (-1) 了，而且 ( ext{lca}(pre,nxt)) 还要 (+1)。另外都已经在插入 (pre,nxt) 时被处理过了。

复杂度 (mathcal O(nlog n))。

代码

( ext{Link.})