题解：P10100 [ROIR 2023 Day 2] 石头

ykzzldz · 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} 卡住。