洛谷P2048 超级钢琴 题解

发表于 | 分类于

题意：
一个有 $n$ 个数的序列，要求找出 $k$ 个长度不小于 $L$ 且不大于 $R$ 的区间，使得它们所对应的区间内数的和最大。

我们的策略肯定是先取最大的，再取次大的，依次类推。

设 $g_{f,l,r}$ 表示左断点为 $f$，右端点在 $[l,r]$ 内的最大值

这个最大值就是 $\max\{sum_x-sum_{f-1}\}(l \leq x \leq r)$

（这里有一个前缀和很容易能看出来）

先考虑 $f$ 一定的情况

把 $sum_{f-1}$ 提出来就是 $\max\{sum_x\}(l \leq x \leq r) - sum_{f - 1}$

现在我们就只用关心 $\max\{sum_x\}(l \leq x \leq r)$

这个用ST表随便搞搞就行

设这个最大值的位置在 $p$ 处取到，

那么次大值可能在 $[l,p-1]$ 或 $[p+1,r]$ 中取到

这个地方用堆随便维护一下就行

然而现在 $f$ 不一定，但我们还是能用堆乱搞维护一下，每次取出一个区间再放回去两个区间

题解写的我自己都看不懂了，或许代码更容易让人理解

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>

using namespace std;

int ST[500010][30], a[500010], s[500010], n, k, l, r, lg_2[500010];

struct orz {
	int l, r1, r2, p, x;
};

struct cmp {
	bool operator () (orz a, orz b) {
		return a.x < b.x;
	}
};

inline orz mk(int l, int r1, int r2, int p, int x) {
	orz res;
	res.l = l;
	res.r1 = r1;
	res.r2 = r2;
	res.p = p;
	res.x = x;
	return res;
}

priority_queue < orz , vector < orz > , cmp > pq;

inline bool is_digit(char c) {
	return c <= '9' && c >= '0';
}

inline int read() {
	char c = getchar();
	int tmp = 0, f = 1;
	while(!is_digit(c)) {
		if(c == '-') f = -f;
		c = getchar();
	}
	while(is_digit(c)) tmp = (tmp << 1) + (tmp << 3) + (c ^ 48), c = getchar();
	return tmp * f;
} 

inline int qry(int l, int r) {
	int len = lg_2[r - l + 1];
	if(s[ST[r - (1 << len) + 1][len]] < s[ST[l][len]]) return ST[l][len];
	return ST[r - (1 << len) + 1][len];
}

inline orz cst(int l, int r1, int r2) {
	int p = qry(r1, r2);
	int x = s[p] - s[l - 1];
	return mk(l, r1, r2, p, x);
}

int main() {
	n = read(), k = read(), l = read(), r = read();
	for(register int i = 1; i <= n; i++) a[i] = read();
	for(register int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
	for(register int i = 1; i <= n; i++) ST[i][0] = i;
	int qwq = 0;
	lg_2[0] = -1;
	for(register int i = 1; i <= n; i++) {
		lg_2[i] = lg_2[i - 1];
		if((1 << qwq) == i) lg_2[i]++, qwq++;
	}
	for(register int i = 1; (1 << i) <= n; i++) {
		for(register int j = 1; j <= n - (1 << i) + 1; j++) {
			if(s[ST[j][i - 1]] > s[ST[j + (1 << i - 1)][i - 1]]) ST[j][i] = ST[j][i - 1];
			else ST[j][i] = ST[j + (1 << i - 1)][i - 1];
		}
	}
	for(register int i = 1; i <= n - l + 1; i++) {
		pq.push(cst(i, i + l - 1, min(i + r - 1, n)));
	}
	long long ans = 0;
	while(k--) {
		orz t = pq.top();
		pq.pop();
		ans += 1ll * t.x;
		if(t.p > t.r1) pq.push(cst(t.l, t.r1, t.p - 1));
		if(t.p < t.r2) pq.push(cst(t.l, t.p + 1, t.r2));
	}
	cout << ans << endl;
	return 0;
}