算法竞赛复健记录

高三学了一年文化课感觉已经不会算法竞赛了，开个博客记录一下复健历程。

CF1662F

题意：有 \(n \le 200000\) 个点，每个点有能量 \(p_i\)，消息能从 \(i\) 传到 \(j\) 当且仅当 \(|i - j| \le \min(p_i, p_j)\)，求消息从 \(a\) 点传到 \(b\) 点至少需要经过几个点。

考虑把点按 \(p_i\) 降序依次插入某个数据结构 \(S\)。当 \(i\) 要插入的时候，将 \(i\) 和 \(\{j \mid j \in S \land i - p_i \le j \le i + p_i\}\) 里的点连边。这里选择可持久化线段树作为 \(S\)，用线段树优化建图的方式连边。时空复杂度是 \(O(n \log n)\)，但是由于实现得不好 MLE 了。

题解的一种做法比较巧妙，直接用线段树优化了 BFS 的过程。本题相当于每条边长度是 1，所以 BFS 时让每个点只访问一遍就可以保证正确性和时间复杂度。对当前 BFS 到的点 \(i\)，它能走到 \(j\) 当且仅当 \(j \in [i - p_i, i) \land i \le j + p_j\)，或者 \(j \in (i, i + p_i] \land i \ge j - p_j\)。对前一情况，用一个支持单点修改、查询区间最大值的线段树 \(S\)，令每个 \(S_j = j + p_j\)，当从 \(i\) 能走到 \(j\) 时，即 \(S.\max[i - p_i, i) \ge i\)，就把 \(j = S.\operatorname{argmax}[i - p_i, i)\) 从线段树里删去，并将 \(j\) 加入 BFS 的队列。后一情况同理。这样的时间复杂度是 \(O(n \log n)\)，空间复杂度是 \(O(n)\)，常数也小，不会 MLE。