「Bzoj 2006」「Noi2010」超级钢琴 (堆 / 主席树+堆)

BZOJ 2006
题意：求序列区间和前$k$大的和。

我题意转化得不好。。我转化成求序列$k$个可重区间和的和，没有体现出本题的贪心思想
然后我们可以发现固定了区间的左端点，那么他的右端点是有固定取值集合的，即$[i+L-1, \min(i+R-1, n)], i+L-1 \leq n$
那么我们先把所有左端点的右端点取值集合弄出来，用ST表维护最大的右端点前缀和，那么这个区间就是最大值的候选答案，加到堆里
然后每次从堆中取出一个区间，加上和以后，删掉这个最优的右端点，继续放进堆作候选答案

当然也可以主席树来做，即每次更新就将那颗树的右端点位置赋值为无穷大，然后这个点不会再影响答案，线段树维护区间最大值即可。
或者直接查询$k$大

知识点
1、左端点的取值集合运用
2、区间和——前缀和

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 500000 + 5;
    const LL LOGS = 20; 

    LL n, k, L, R, a[MAXN], st[MAXN][LOGS + 1];

    LL mymin(LL x, LL y) {return a[x] > a[y] ? x : y;}
    LL query(LL l, LL r) {
        LL k = log2(r - l + 1);
        return mymin(st[l][k], st[r - (1 << k) + 1][k]);
    }

    struct data {
        LL l, r, u, v;
        data(LL xl, LL xr, LL xu) {
            l = xl, r = xr, u = xu, v = query(l, r);
        }
        bool operator < (const data &rhs) const {return a[v] - a[u] < a[rhs.v] - a[rhs.u];}
    };
    priority_queue<data > q;

    void clean() {
    }
    int solve() {

        clean();
        cin >> n >> k >> L >> R;
        for (LL i = 1; i <= n; ++i) scanf("%lld", &a[i]), a[i] += a[i - 1], st[i][0] = i;
        for (LL j = 1; (1 << j) <= n; ++j) {
            for (LL i = 1; i + (1 << j) - 1 <= n; ++i) {
                st[i][j] = mymin(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
        for (LL l = 1; l <= n; ++l) 
            if (l + L - 1 <= n) {
                data p(l + L - 1, min(l + R - 1, n), l - 1);
                q.push(p);
            }

        LL ans = 0;
        for (LL i = 1; i <= k; ++i) {
            data u = q.top(); q.pop();
            ans += a[u.v] - a[u.u];
            data p1(u.l, u.v - 1, u.u);
            data p2(u.v + 1, u.r, u.u);
            if (u.l <= u.v - 1) q.push(p1);
            if (u.v + 1 <= u.r) q.push(p2);
        }
        cout << ans;

        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}