P8539 「Wdoi-2」来自地上的支援

P8539 「Wdoi-2」来自地上的支援

移项维护特殊值。

这题思路还是挺简单的。

首先分析操作。发现操作序列一定是单调递增的，也就是每个数只会被选中连续几次，之后就不会再被选中了。

然后分析询问。我们发现要满足条件，\(x\) 显然是在 \([x, x+k-1]\) 被选中。

那么首先 \(x+k-1>n\) 一定无解。

要满足在第 \(x\) 次操作被选中，设 \(mx_x\) 为前 \(1\) 到 \(x-1\) 次操作完的操作序列结尾（也就是操作完后 \([1,x-1]\) 中的最大值），那么有 \(a_x\ge mx\)。（相等显然可以被选）

要在之后的 \([x+1,x+k-1]\) 中被选中，满足对于 \(j\in [x+1,x+k-1]\)，有 \(a_i+(j-i)\times v>a_j\)，根据维护技巧移项，即 \(a_i-i\times v>a_j-j\times v\)。所以我们只需要求出最大的 \(a_j-j\times v\) 即可。

考虑线段树，因为 st 表空间爆了。于是每个询问的答案即为 \(ans=\max(mx_x,query(x+1,x+k-1)+i\times v+1)\)。

注意是大于号，要加 \(1\)。

复杂度 \(O(n+m\log n)\)，由于时限为 2s，算稳吧。

这题有线性做法，但就是绕一点。