呱呱呱！
目录
- $\text{[ONTAK 2010] Peaks}$
- 解法
- 代码
- 训练士兵
- $\text{Couple Trees}$
- 题目描述
- $\text{JZOJ - 4616}$ 二进制的世界
- $\text{K }$个串
- $\text{BZOJ - 4771 }$七彩树
\(\text{[ONTAK 2010] Peaks}\)
首先可以想到是 \(\rm Kruskal\) 重构树，问题转化为求重构树中某子树的第 \(k\) 大权值。
先开始想写线段树合并，后来发现要写可持久化，不然由于中间的版本将地址给了后面的版本，就不能查询中间版本了。
其实这题也可以用 \(\rm dfs\) 序解决，将子树转化成序列问题。对于本来就有的点，加入自己；对于每个重构树新增的点，记录 \(st,ed\)，最后查询这个区间中的答案即可。
\(\text{Link.}\)
将询问和修改差分。令修改 \((x,y,w)\) 表示将横纵坐标都分别大于 \(x,y\) 的点都加上 \(w\)。这样我们需要考虑 \((x,y,w)\) 对 \([1,1]-[i,j]\) 的贡献
\[\text{Ans}=\sum_{x=1}^i\sum_{y=1}^j (i-x+1)\cdot (j-y+1)\cdot w_{x,y}
\]
\[=(i+1)(j+1)\cdot \sum_{x=1}^i\sum_{y=1}^j w_{x,y}-(j+1)\cdot \sum_{x=1}^i\sum_{y=1}^j x\cdot w_{x,y}-(i+1)\cdot \sum_{x=1}^i\sum_{y=1}^j y\cdot w_{x,y}+\sum_{x=1}^i\sum_{y=1}^j xy\cdot w_{x,y}
所以只需要维护四个变量即可。
由于是先修改再查询，我们可以不使用树套树，而是将 \(x,y\) 坐标离散化后，以 \(x\) 坐标为主席树的根，将 \(y\) 在主席树上维护。查询也是 \(\mathcal O(q\log n)\) 的。
\(\text{Couple Trees}\)
给定两棵大小均为 \(n\) 的树，它们共用相同的节点。保证 父亲的编号一定比儿子小。
有 \(m\) 个询问，每个询问为 \((x,y)\)，询问从树 \(1\) 的 \(x\)，树 \(2\) 的 \(y\) 开始向上走，能走到相同 \(\rm id\) 的最深的点。你需要输出这个点以及 \(x,y\) 到这个点的步数。
可以先将树 \(1\) 来一个树剖，这样 \(x\) 到根的路径可以被表示成几段区间。对树 \(2\) 做主席树，儿子继承父亲的版本，在树 \(1\) 的 \(\text{dfn}_x\) 的地方插入 \(x\)。这样对于查询，我们可以在第 \(y\) 个版本的主席树中查询 \(x\) 到根路径被表示的区间，这是 \(\mathcal O(q\log^2 n)\) 的。
\(\text{JZOJ - 4616}\) 二进制的世界
给定长为 \(n\) 的序列 \(a\)，你需要对于每个 \(i\in[2,n]\)，求出 \(a_i\text{ opt }a_j\) 的最大值，其中 \(j\in[1,i)\)，\(\text{opt}\in \{\text{or,and,xor}\}\)。
\(n\le 10^5,0\le 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\text{ opt }y\}
假设询问的数字前后 \(8\) 位分别为 \(x,y\)，就有
\[\text{Ans}=\max\big \{f_{i,y}+(i\text{ opt }x)\cdot 2^8\big \}
\(\text{K }\)个串
题目是比较经典的堆的问题，因为 \(k\le 2\cdot 10^5\)，我们可以以 \(i\in[1,n]\) 作为右端点，先将右端点为 \(i\) 的最大子串塞进堆，取出堆顶，发现最大子串将左端点区间分成两段，在两段中各取最大值即可。
问题是如何快速维护右端点为 \(i\)，左端点在某一区间的最大子串。可以考虑以右端点为根建立主席树，左端点对应着树内下标。这样每次右移右端点 \(i\)，它的贡献就是在 \((lst_{a_i},i]\) 中加上 \(a_i\)。
实现上为了控制内存，写了个标记永久化（这样每次还是增加大概 \(\log n\) 个点），记录一下几个小 \(\rm bug\)：
- 在
ins()
pushUp()
ask()
- 每次修改区间之后，不能直接将 \(rt_i\) 的最大值塞进堆。这也是写法的问题，因为 \(rt_i\) 是 \([1,n]\) 的最大值，而 \([i+1,n]\) 初始是 \(0\)，如果 \([1,i]\) 区间内的数都 \(<0\) 就会出错。
\(\text{BZOJ - 4771 }\)七彩树