Luogu P2048 [NOI2010]超级钢琴

题目链接：​​传送门​​

#include <bits/stdc++.h>

using namespace std;
int n, k, l, r, ans, s[500010];
priority_queue<int> q;

int main(int argc, char const *argv[]) {
  cin >> n >> k >> l >> r;
  for (int i = 1; i <= n; i++) scanf("%d", &s[i]), s[i] += s[i - 1];
  for (int len = l; len <= r; len++)
    for (int start = 1; start + len - 1 <= n; start++)
      q.push(s[start + len - 1] - s[start - 1]);
  while (k--) ans += q.top(), q.pop();
  cout << ans << endl;
}      

/**
 * @Date:   2019-10-05T15:33:03+08:00
 * @Last modified time: 2019-10-05T19:03:52+08:00
 */
#include <bits/stdc++.h>
#define
#define

using namespace std;
typedef long long ll;
int n, k, l, r; ll a[A], f[A][20], ans;
struct node {
    int s, l, r, t;
    friend bool operator < (const node x, const node b) {return a[x.t] - a[x.s - 1] < a[b.t] - a[b.s - 1];}
};
int maxx(int x, int y) {return a[x] > a[y] ? x : y;}
int ask(int x, int y) {
    int k = log2(y - x + 1);
    return maxx(f[x][k], f[y - (1 << k) + 1][k]);
}
priority_queue<node> q;

int main(int argc, char const *argv[]) {
    cin >> n >> k >> l >> r;
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), f[i][0] = i, a[i] += a[i - 1];
    for (int j = 1; 1 << j <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            f[i][j] = maxx(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    for (int i = 1; i + l - 1 <= n; i++) q.push(node{i, i + l - 1, min(i + r - 1, n), ask(i + l - 1, min(n, i + r - 1))});
    while (k--) {
        node fr = q.top(); q.pop(); ans += a[fr.t] - a[fr.s - 1];
        if (fr.l != fr.t) q.push(node{fr.s, fr.l, fr.t - 1, ask(fr.l, fr.t - 1)});
        if (fr.r != fr.t) q.push(node{fr.s, fr.t + 1, fr.r, ask(fr.t + 1, fr.r)});
    }
    cout << ans << endl;
    return 0;
}
/*
10 13 3 7
595
384
-435
-197
-677
661
4
-100
-653
220

1112
*/