Ynoi 切（受）题（虐）记录

防止忘记做法大致按照切题顺序简略写一下思路，同时造福一下社会。（不过我怀疑大概只有我能看懂我自己写的。）缓慢更新。

1. P4119 [Ynoi2018] 未来日记

   最初分块。

   人生第一道 Ynoi 和大分块（之前只做过小分块）。也是目前最喜欢的题，感觉思路非常优美。

   序列分块套值域分块。统计次数并做前缀和。修改次数时再做一次差分恢复成原次数数组，改完之后再前缀和回去。同时块内重标号，修改时散块暴力重构；对于整块，如果不会发生合并就直接改标号，会合并就直接暴力重构。考虑发生重构的次数只与块内数字种类数有关，而所有块数字种类最多为 \(O(n+m)\)，每次重构复杂度为 \(O(\sqrt n)\)，因此总复杂度 \(O((n+m)\sqrt n)\)。

   感觉这个写法比很多人写的并查集写法要优美很多，而且复杂度少了个 \(\alpha(n)\)。

   难度梯度：T2。（Ynoi 内部排序。最高 T0，最低 T4 或者 T5。）

2. P4117 [Ynoi2018] 五彩斑斓的世界

   第二分块。

   分块套并查集。每次操作即为将 \((i,i-x)\) 两种数合并。块内重标号。通过打区间加 tag 使得并查集根节点个数只减不增。所以每块只会发生 \(O(\sqrt n)\) 次合并。时间复杂度 \(O((n+m) \sqrt n)\)（本题特殊性质使得并查集复杂度 \(O(1)\)。）空间复杂度 \(O(n \sqrt n)\)，会爆。考虑离线逐块处理去一个根号。

   难度梯度：T2.5

3. P5064 [Ynoi2014] 等这场战争结束之后

   建操作树，在操作树上 DFS。用可撤销并查集维护连通性。顺便维护并查集的时候维护一个值域分块。当块长取 \(O\left(\sqrt {\frac{n}{\log n}}\right)\) 时，时间复杂度 \(O(m \sqrt {n \log n})\)。空间复杂度 \(O(m \sqrt n)\)。理论不可过，但是可以调块长以及用 short 卡过去。

   存在空间 \(O(n)\) 的解法（逐块处理，懒得写）。时间 \(O(n\sqrt n)\) 的做法（top cluster）。

   难度梯度：T3。如果本题 lxl 加强数据使得必须用最优理论时空复杂度才能过的话难度梯度 T1。

之后的有缘在写。