传送门

题目描述

小Z是一个小有名气的钢琴家，最近C博士送给了小Z一架超级钢琴，小Z希望能够用这架钢琴创作出世界上最美妙的音乐。
这架超级钢琴可以弹奏出n个音符，编号为1至n。第i个音符的美妙度为Ai，其中Ai可正可负。一个“超级***”由若干个编号连续的音符组成，包含的音符个数不少于L且不多于R。我们定义超级***的美妙度为其包含的所有音符的美妙度之和。两个超级***被认为是相同的，当且仅当这两个超级***所包含的音符集合是相同的。小Z决定创作一首由k个超级***组成的乐曲，为了使得乐曲更加动听，小Z要求该乐曲由k个不同的超级***组成。我们定义一首乐曲的美妙度为其所包含的所有超级***的美妙度之和。小Z想知道他能够创作出来的乐曲美妙度最大值是多少。

输入格式：

输入第一行包含四个正整数n, k, L, R。其中n为音符的个数，k为乐曲所包含的超级***个数，L和R分别是超级***所包含音符个数的下限和上限。接下来n行，每行包含一个整数Ai，表示按编号从小到大每个音符的美妙度。

输出格式：

输出只有一个整数，表示乐曲美妙度的最大值。

解题思路：要求查找前k个最大的区间和(满足区间长度 l <=lenght <= r)，区间和很容易想到前缀和做差，我们可以利用主席树来维护前缀和。我们可以先确定区间右端点(右端点前缀和pre_r)，然后再符合条件的左端点区间中找到最小值(pre_l)。把每一个区间都放入优先队列中去维护，如果我们用到了这个区间的第K小，那么我们下一步就要将这个区间中的第K+1小再放入队列中继续中维护。这个用优先队列来维护最大的思路很巧妙，原来做过类似的题居然没有想到。。。。优先队列维护最小值

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 5e5 + 5;

int pre[maxn], ranks[maxn], d;
struct node {
    int ls, rs, cnt;
#define left(a, b) p[a].ls, p[b].ls, l, mid
#define right(a, b) p[a].rs, p[b].rs, mid + 1, r
} p[maxn * 80];
int root[maxn], times;

void insert(int &now, int old, int l, int r, int x) {
    now = ++times;
    p[now] = p[old], p[now].cnt++;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid) insert(left(now, old), x);
    else insert(right(now, old), x);
}

int query(int sta, int end, int l, int r, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1, x = p[p[end].ls].cnt - p[p[sta].ls].cnt;
    if (k <= x) return query(left(sta, end), k);
    else return query(right(sta, end), k - x);
}

struct state {
    int l, r, prefix, minn, k;

    bool friend operator<(state a, state b) {
        return a.prefix - a.minn < b.prefix - b.minn;
    }
} now, temp;

int get_pos(int x) {
    return lower_bound(ranks + 1, ranks + 1 + d, x) - ranks;
}

int main() {
    pre[0] = 0;
    int n, k, l, r, x, a, b;
    ll ans = 0;
    scanf("%d %d %d %d", &n, &k, &l, &r);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        pre[i] = pre[i - 1] + x;
        ranks[i] = pre[i];
    }
    ranks[n + 1] = 0;   ///前缀和中还有0
    sort(ranks + 1, ranks + 1 + n + 1);
    d = unique(ranks + 1, ranks + 1 + n + 1) - (ranks + 1);
    insert(root[0], 0, 1, d, get_pos(pre[0]));
    for (int i = 1; i <= n; i++) insert(root[i], root[i - 1], 1, d, get_pos(pre[i]));
    priority_queue<state> q;
    for (int i = 1; i <= n; i++) {
        if (i < l) continue;
        b = i - l, a = max(i - r - 1, -1);  ///确定需要查找的前缀和区间(a,b]
        now.l = a, now.r = b;
        now.prefix = pre[i], now.k = 1;
        now.minn = ranks[query(a == -1 ? 0 : root[a], root[b], 1, d, 1)];
        q.push(now);
    }
    while (k--) {
        now = q.top();
        q.pop();
        ans = ans + now.prefix - now.minn;
        if (now.k == now.r - now.l) continue;   ///如果达到了区间的上限
        now.minn = ranks[query(now.l == -1 ? 0 : root[now.l], root[now.r], 1, d, ++now.k)];
        q.push(now);
    }
    printf("%lld\n", ans);
    return 0;
}