NOI2010 超级钢琴

题面

给定一个长度为 $n$ 的序列,求长度在 $[L,R]$ 范围内的子区间权值和的前 $k$ 大之和。

其中 $1 \le n,k \le 5 \times 10^5$。

分析

前 $k$ 大等价于每次选一个没有选择过的子区间中有最大权值的。

记三元组 $(o,l,r)$ 表示左端点为 $o$,右端点在区间 $[l,r]$ 范围内的一段区间,即询问 $[l,r]$ 范围内前缀和的最大值,RMQ 预处理。

用一个堆来维护最大值,显然当前时刻的最大值对应某一个三元组 $(i,L,R)$。

当我们删除这个三元组时,还需要考虑 $i$ 为左端点的其它情况。

设最大值位置为 $t$,那么可能存在次大值在 $(i,L,t-1)$ 和 $(i,t+1,R)$,特判区间是否存在,加进堆里维护。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 500000 + 5;

int n, k, L, R, a[maxn];

int dp[maxn][21];
void init() {
for (int i = 1; i <= n; i++) dp[i][0] = i;
for (int j = 1; j < 21; j++) {
for (int i = 1; i + (1 << j) <= n + 1; i++) {
int x = dp[i][j - 1], y = dp[i + (1 << (j - 1))][j - 1];
dp[i][j] = a[x] > a[y] ? x : y;
}
}
}
int query(int l, int r) {
int k = log2(r - l + 1);
int x = dp[l][k], y = dp[r - (1 << k) + 1][k];
return a[x] > a[y] ? x : y;
}

struct node {
int o, l, r, t;
node(int oo, int ll, int rr) {
o = oo; l = ll; r = rr;
t = query(l, r);
}
bool operator < (const node& b) const {
return a[t] - a[o - 1] < a[b.t] - a[b.o - 1];
}
};

int main() {
scanf("%d%d%d%d", &n, &k, &L, &R);
for (int i = 1; i <= n; i++) scanf("%d", a + i), a[i] += a[i - 1];
init();
priority_queue<node> pq;
for (int i = 1; i + L - 1 <= n; i++) {
pq.push(node(i, i + L - 1, min(n, i + R - 1)));
}
ll ans = 0;
while (k--) {
node tp = pq.top(); pq.pop();
ans += a[tp.t] - a[tp.o - 1];
if (tp.l < tp.t) pq.push(node(tp.o, tp.l, tp.t - 1));
if (tp.t < tp.r) pq.push(node(tp.o, tp.t + 1, tp.r));
}
cout << ans << endl;
return 0;
}