自动搬运

查看原文

来自洛谷，原作者为

	ykzzldz 做自己，别管别人

搬运于2025-08-24 22:54:40，当前版本为作者最后更新于2024-11-04 14:44:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先给出一个显然的结论，对于一次询问 $(p,k)$，若答案不为 $0$，则有 $[p-k+1,p]$ 或 $[p,p+k-1]$ 被取完。由于这两部分没有本质区别，我们只讨论右区间的情况。

首先，若 $a_{p+k}<a_p$，答案为 $0$，下面我们不再考虑这种情况。我们设 $[p,p+k-1]$ 的最大值位置为 $pos$，那么在 $pos$ 左边的数肯定是不能贡献答案的。

先考虑 $a_{p+k}>a_{pos}$ 的情况，若从 $pos$ 右侧开始染色，染色会在 $pos$ 位置被卡住，也就是说，会先染 $[pos+1,p+k-1]$ 这一段，所以这一段都能被贡献进答案中。单独考虑 $pos$ 位置，发现其能被贡献进答案当且仅当区间内 $pos$ 左侧有一个位置的值大于右侧的所有值，这样可以在这个左侧的位置被卡住。

再考虑 $a_{p+k}<a_{pos}$ 的情况，这种情况下只有 $pos$ 位置可能被贡献进答案。此时，应满足区间内 $pos$ 左侧有一个位置大于右侧的所有值且区间内除 $pos$ 位置外其他值都应该比 $a_{p+k}$ 小，这样才能被 $a_{p+k}$ 卡住。