[NOI2010]超级钢琴 题解

题目

题意简述：

给定一个序列 $a$，选出其中 $k$ 段连续子序列，要求每一段连续子序列长度在 $l$ 和 $r$ 之间，求 $k$ 段连续子序列和的最大值。

$n,k\le 5\cdot 10^5,a_i\le 1000$

思路

对于所有未选的子序列，以 $o$ 为起点的子序列可以求出一个唯一最值，假设长度为 $t(l\le t\le r)$，由于 $o$ 是定点，所以我们尽量使 $su{m}_{l+t-1}$ 最大即可使得序列和最大为 $su{m}_{l+t-1}-su{m}_{o-1}$（$su{m}_i={\sum }_{k=1}^i{a}_k$）。

我们设置一个结构体类型来代表一个最大区间，存储起点，序列长度下限和上限，总和最大时的序列长度，由于最大长度为 $sum$ 数组中某区间的最大值的位置，于是可以用 RMQ/线段树维护。用堆维护最大区间，每一次取出，还要放入两个区间，其中一个下限不变，上限变为原区间右端点减一，另外一个上限不变，下限变为原区间右端点加一，注意特判原序列长度为 $1$ 或者长度上限的情况。

最后输出答案，别忘了开 long long。

AC Code：

#include <bits/stdc++.h>
using namespace std;
int n, k, l, r;
int a[500100];
long long sum[500100];
// 线段树
struct node{
int l, r;
long long maxx;
int idx;
};
node t[4000100];
void maketree(int l, int r, int p) {
t[p].l = l, t[p].r = r;
if (l < r) {
maketree(l, (l + r) / 2, p * 2);
maketree((l + r) / 2 + 1, r, p * 2 + 1);
if (t[p * 2].maxx > t[p * 2 + 1].maxx) {
t[p].maxx = t[p * 2].maxx, t[p].idx = t[p * 2].idx;
}
else {
t[p].maxx = t[p * 2 + 1].maxx, t[p].idx = t[p * 2 + 1].idx;
}
}
else
t[p].maxx = sum[l], t[p].idx = l;
}
pair<long long, int> get(int l, int r, int p) {
if (t[p].l > r || t[p].r < l) return {-0x3f3f3f3f, 0};
if (l <= t[p].l && t[p].r <= r) return {t[p].maxx, t[p].idx};
pair<long long, int> p1 = get(l, r, p * 2), p2 = get(l, r, p * 2 + 1);
return p1.first > p2.first ? p1 : p2;
}
// 区间信息
struct node1{
int o, l, r, t;
void renew() {
t = get(o + l - 1, o + r - 1, 1).second - o + 1;
}
};
bool operator <(node1 a, node1 b) {
return sum[a.t + a.o - 1] - sum[a.o - 1] < sum[b.t + b.o - 1] - sum[b.o - 1];
}
priority_queue<node1> q;
long long ans;

int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k >> l >> r;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
}
maketree(1, n, 1);
for (int i = 1; i <= n; i++) {
if (i + l - 1 > n) continue;
node1 tmp = {i, l, min(r, n - i + 1)};
tmp.renew();
q.push(tmp);
}
for (int i = 1; i <= k; i++) {
node1 now = q.top();
q.pop();
ans += sum[now.t + now.o - 1] - sum[now.o - 1];
// 放入两个新的区间。
if (now.t > now.l) {
node1 p = {now.o, now.l, now.t - 1};
p.renew();
q.push(p);
}
if (now.t < now.r) {
node1 p = {now.o, now.t + 1, now.r};
p.renew();
q.push(p);
}
}

cout << ans << '\n';
return 0;
}

原文地址：https://blog.csdn.net/m0_72961775/article/details/140705220

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！