题解：CF2138D Antiamuny and Slider Movement

nullqtr_pwp · 2025-09-15 20:43:13 · 题解

维护所有点当前的位置 a，当 x\leq a_i 时，对 j\leq i 的 a_j 与 x-i+j 做 \text{chkmin}，否则对 j\ge i 的 a_j 与 x-i+j 做 \text{chkmax}。考虑 a_i\to a_i-i,q_x\to q_x-q_i 以抵消移位的影响，此时操作就是对前缀的 x 做 \text{chkmin} 或者对后缀的 x 做 \text{chkmax}，由于 a 单调不降所以是推平。

考虑直接转 01，设定阈值 k 考虑是否有 a_i\ge k，操作转化为 x<k 则前缀推平为 0，否则后缀推平为 1。本质不同的 k 只有 \mathcal O(n+q) 个，可以直接枚举。取出 0,1 操作中分别最长的长度，若两者不交那么平凡；否则，维护 01 分界线位置 p，则给定了若干 p 对 b_i 取 \min,\max 的操作。内部再做一次 01，求 p 最终 \ge lim 的方案数，求一下个数即可。时间复杂度 \mathcal O((n+q)^2)。