CF207B3 Military Trainings 题解

tder · 2024-11-22 11:56:46 · 题解

You can view the English version of this solution.

图片托管于 Github，若加载失败请使用加速器。

首先容易想到把序列复制一遍，破环为链，每个询问即查询子段答案。

设 f_i 能从 j=x 或 j=y 转移而来，考虑一个贪心。

其中 P(k) 表示 f_k 能从哪些点转移而来，即 P(k)=[k-p_k,k-1]。

由于 k-1\in P(k) 恒成立，我们无需考虑 [i-p_i,k-1] 这段区间的贡献。而 [y-p_y,i-p_i]\subseteq[x-p_x,i-p_i]，即所有能转移到 y 的点都能转移到 x，因此选择从 x 转移而来即可。这也就是说，从 k-p_k 较小的 k 转移来是不劣的。用 ST 表维护之，复杂度 \mathcal{O}(n\log n+\text{ans})。

你交了一发，并发现这个东西在模拟赛过了。可以使用倍增预处理出跳 2^n 步能跳到哪，优化成 \mathcal{O}(n\log n)。