分块代替思考

· · 题解

根号老哥过了。

先建 PAM，则直接转化为一个树上问题：

给定你一个 n 个节点的树，以 1 为根，每个节点有一个固定权值 len_i\le 2n，保证 \forall u\in[2,n],len_u>len_{fa_u}，还有权值 b_i，初始为 0。

1. 给定 $(x,y,c)$，把路径 $(x,y)$ 染色为 $c$，即 $\forall u\in road(x,y),b_u\gets \max(b_u,c)$。 2. 给定 $x$，查询最大的 $k$ 使得存在 $\exist{i},{len_i=k\wedge b_i-len_i\ge x}$。 对于一条重链，我们要做区间覆盖，直接对链分块，每次做区间覆盖即可做到 $\mathcal{O}(\sqrt{n})-\mathcal{O}(1)$。注：每条重链单独分块，链长至少翻倍，则总复杂度为根号。 把所有点按照 $len_i$ 升序排序。对这个序列分块，记 $bel_i$ 为 $i$ 所在的块标号，对于每个点 $u$，记 $nxt_u$ 为：祖先中深度最浅的点 $v$ 使得 $bel_v=bel_u$，则我们每次只需要从修改底部跳 $nxt$ 即可，复杂度 $\mathcal{O}(q\sqrt{n})$。 --- 回到本题，模拟一下扫描线的过程，每次是要对一段链前缀做 1 操作，这个可以用 LCT 或 dsu on tree 求出，然后做分块即可做到 $\mathcal{O}(q\sqrt{n}\log n)$。 由于每次修改的到根链是有祖先关系的，可能可以入手优化，但是不优化已经可以通过。 [AC link](https://codeforces.com/contest/2164/submission/353133145).