自动搬运

查看原文

来自洛谷，原作者为

	dspt その日まで 飛ばあげ 嵐がさわってゆくまで

搬运于2025-08-24 22:02:27，当前版本为作者最后更新于2022-05-06 20:19:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Start

前置知识：树状数组

区间修改，单点查询。

1.思路

看到各个大佬们用的都是 FHQ、Splay、权值线段树等高级数据结构，我自愧弗如。

但是我可以用简单基本的算法吊打：树状数组。

现在所有通过的程序中，最优解速度第 4（没有开 O2，快读等优化），空间 & 码量都是最小的。

2.建树

根据差分，树状数组 $b_i=a_i-a_{i-1}$，先把 $a_i$ 数组排序，然后依次单点修改：add(i, a[i] - a[i - 1])。但是我们在查询中就会有一个问题：我们无法知道 $\min$ 和 $\max$ 在 $b$ 这个不下降数组的位置？于是我们写两个二分函数 left(x) 和 right(x)。

left：查询 sum(i) >= x 时 $i$ 的最大值，即最后一个前缀和 $\ge x$ 的位置。

right：查询 sum(i) <= x 时 $i$ 的最小值，即第一个前缀和 $\le x$ 的位置。

这两个函数在修改中必不可少。

3.修改

查询很简单，前面说了，考虑如何修改。

修改最重要的就是有一些高度相同的树，只有一部分修改，另一部分不修改（样例第一个输出），如何处理？

假设修改操作的两个输入分别是 $x,y$，那么我们先算出找到要修改的数的值得区间 $[x,s]$，s = sum(x + left(y) - 1)，很好理解。

接下来分成两段处理，一段是值在 $[x,s-1]$ 中的，另一段是值为 $s$ 的。具体代码：

const int z(left(y)), s(sum(x + z - 1)), l(left(s)), r(right(s));
add(z, 1), add(l, -1);
add(l + r - x - z + 1, 1), add(r + 1, -1);

End

特判：

1. 查询的范围在 $a$ 中最大值与最小值之外
2. 需要修改的数的数量大于符合范围的数的数量

代码