6717-牛逼做法

dottle · 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。矛盾。