自动搬运

查看原文

来自洛谷，原作者为

	Edgration **

搬运于2025-08-24 21:54:28，当前版本为作者最后更新于2017-11-03 15:05:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

还是本题的出题人我来发一个题解吧。。

这个题作为考试的第一题，是个心态题。

所谓的树状数组和线段树都是不存在的。

实际上只需暴力轻松解决。

首先暴力有66~70分。

对于Final操作

然后，类似前缀和，记录下来这个位置之前有几个满足条件的数的个数 ，这样有88~90分。

因为修改多，查询少，如果可以优化修改操作就可以AC了，显然上个差分

O(1)修改，差分维护数组，区间加的时候 a[L]+=x,a[R]-=x

总复杂度O(n*1000) （1000次修改），拿到100分

程序我就不发了，就是题目下面的标程