[NOI2010] 超级钢琴 主席树+前缀和+优先队列

Problem Analysis

区间和问题，我们可以首先转化为前缀和形式，每个区间的和就可以表示出来；然后我们枚举每个区间左端点，对于每个左端点计算 a [ i + j − 1 ] − a [ i − 1 ] ( j ∈ [ L , R ] ) a[i + j - 1] - a[i - 1](j \in [L, R]) a[i+j−1]−a[i−1](j∈[L,R])。

由于每次我们枚举左端点的时候，使左端点固定不变，那么对于左端点为起点的第 k k k大区间和就等于右边第 k k k大的前缀和减去左端点前一个点的前缀和。

那么我们首先从所有区间的最大区间和中找出最大的区间，然后不停的查询至 k k k个区间全部集齐即可。

Accepted Code

#include 
#define ll long long
using namespace std;

int n, k, un, HL, HR;
const int N = 5e5 + 10;
int a[N], b[N], root[N], tot = 0;
int sum[N  k >> HL >> HR; n += 1;
    for(int i = 2; i > a[i];
        a[i] += a[i - 1];
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    un = unique(b + 1, b + 1 + n) - (b + 1);
    for(int i = 1; i