「NOI 2010」超级钢琴

题目大意：

选取前 $k$ 大/小的时候，要借鉴这种先把每个位置最优的元素放入堆中，然后边取边分裂的思想。

#include <cstdio>
#include <queue>
#include <cmath>

const int N = 500005;
int n, m, l, r, sum[N], st[N][20]; long long ans;
struct Node {
    int x, y, l, r; //x表示此时左端点的位置, y表示右端点, [l,r]表示右端点的范围
    bool operator < (const Node &rhs) const {
        return sum[y] - sum[x-1] < sum[rhs.y] - sum[rhs.x-1];
    }
};
std::priority_queue<Node> Q;

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
int max(int x, int y) {
    return sum[x] > sum[y] ? x : y;
}
int min(int x, int y) {
    return x < y ? x : y;
}
void previous() {
    for (int j = 1; j <= 19; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            st[i][j] = max(st[i][j-1], st[i+(1<<j-1)][j-1]);
}
int query(int l, int r) {
    if (l > r) return -1;
    int k = log2(r - l + 1);
    return max(st[l][k], st[r-(1<<k)+1][k]);
}

int main() {
    n = read(), m = read(), l = read(), r = read();
    for (int i = 1; i <= n; ++i)
        sum[i] = sum[i-1] + read(), st[i][0] = i;
    previous();
    for (int i = 1; i + l - 1 <= n; ++i) {
        int x = i + l - 1, y = min(n, i + r - 1);
        Q.push((Node){i, query(x, y), x, y});
    }
    while (m--) {
        Node now = Q.top(); Q.pop();
        ans += sum[now.y] - sum[now.x-1];
        if (now.y > now.l) Q.push((Node){now.x, query(now.l, now.y-1), now.l, now.y-1});
        if (now.y < now.r) Q.push((Node){now.x, query(now.y+1, now.r), now.y+1, now.r});
    }
    printf("%lld\n", ans);
    return 0;
}

时间复杂度 $O((n+m) \log n)$