自动搬运

查看原文

来自洛谷，原作者为

	dottle Cy@?g|^a

搬运于2025-08-24 22:23:20，当前版本为作者最后更新于2022-07-28 17:43:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

问题相当于求两个距离不大于 $K$ 的数对的和的最大值。

将序列 $K$ 个分一块，对于每个块内的最大值，钦定他们是最大值或次大值之一，然后求出他们周围 $K-1$ 个数的最大值，用他们的和更新答案。

一开始的最大值使用单调队列求出。每次修改，只需要重新求出块内最大值，然后重新计算周围 $O(1)$ 块的信息。使用线段树维护区间最大值即可。

时间复杂度 $O(n+q\log n )$。

证明，我们最担心出现这样的情况：答案是相邻两个块的两个非最大值的数匹配。设他们为 $a,b$，所在块的分别的最大值为 $c,d$，有 $c>a,d>b$。考虑 $a$ 和 $c$ 而不是 $b$ 匹配，所以 $b>c$；$b$ 与 $a$ 而不是 $d$ 匹配，所以 $a>d$。矛盾。