退役了，平时没事干就做点题吧，但是这里只会记录一些我觉得非常好的题。
[NWRRC 2025] Keys and Grates
在数轴上，有 \(n\) 个不同的障碍，每个障碍唯一对应了一把钥匙，散落在不同位置。
你要从 \(S\) 走到 \(T\)，求最短路径，或者报告无解。
\(n \le 2 \cdot 10^5\)
手玩一下，观察到我们的路径一定是左右往返。有很多做法，这里学到一个非常巧妙的建图方法：
- 从 \(S\) 开始向两侧的点连边，左侧向左侧相邻的位置连有向边，右侧向右侧相邻的位置连有向边；
- 钥匙向门连有向边；
我们从 \(S\) 开始，做拓扑排序，有解的充要条件是 \(T\) 可以被入队。
这是因为 \(T\) 想要入队，必须能从一侧抵达；门想要入队，必须同时满足能从一侧抵达，且能从钥匙抵达。
同时，在这个这个过程中，求出 \(S\) 到 \(T\) 的 最长路 即为答案。
这是因为前面说了，每个门有两个限制都要满足，其他的则为一个。从定义来看，恰好是最长路。
笔记：存在多个限制要同时满足，则瓶颈是最晚满足的那个限制，故可以得到最长路的建模。
[Ynoi2007] rfplca
给一棵以 \(1\) 为根的树，定义 \(a_i\) 是点 \(i\) 的父亲，满足父亲的编号一定小于自己，有 \(m\) 次操作：
- 区间减法，但不会小于 \(1\)，即 \(\text{max}(a_i - x, 1)\)
- 查询两个点的 LCA
\(n,m\le 4 \cdot 10^5\)
这个题好像在 \(23\) 还是 \(24\) 年的 \(\text{icpc}\) 里原了（可能是转化完以后），我赛时就没读到这个题，赛后听别人说的，正好退役了，补一下这个题。
考虑如果能满足 \(i - a_i \ge \sqrt n\)，那么树高也不超过根号，这个时候暴力查询复杂度就是对的，和树剖的跳法类似。这个限制还能稍微放松一下，我们对编号分块以后，如果 \(a_i\) 和 \(i\) 不在一个块里，那么就认为它已经满足了特殊条件（因为暴力跳的时候，一共只有根号个块可以切换），相当于是找了一个简易的势能。
现在考虑如果 \(i - a_i\) 很小怎么办，实际上如果写过弹飞绵羊这个题的话，应该马上就会了。我们再设计 \(h_i\) 表示从 \(i\) 出发一直跳，首次跳出自己这个块，抵达的编号。
修改的时候，我们记录每个块被完整地修改了几次，如果减了超过根号次，这个 \(h\) 必然是和 \(a\) 一样的，就不需要单独维护了。否则我们直接重构整个块的每个 \(h\)，这样每个块只会重构根号次，于是就做完了。注意如果重构的是散块，那么要一直重构到这个块的尾部（块的后半部分也会被前半部分的修改影响）。