【NOI2010】 超级钢琴 线段树+堆

[2006: [NOI2010]超级钢琴][1]

一句话题意：计算出所有区间和中前K大

题解：
显然根据题目要求我们需要在$O(NlogN)$的时间复杂度内解决这个问题。

首先我们枚举左端点L，然后设区间右端点处在[qL,qR]这个区间。我们需要在$O(logN)$的时间复杂度内计算出从左端点到右端点区间和的最大值。如何快速的计算出这个最大值以及最大值所在的位置呢？

预处理出前缀和，这样的话我们上述问题就变成了$max(sum[R])-sum[L-1](R\in [qL,qR])$,显然我们只需要求出$sum[qL]……sum[qR]$中的最大值然后减去$sum[L-1]$

于是根据上述性质使用ST表或者是线段树维护一个二元组$(ans,i)$代表区间$sum[i]$的最大值和取到最大值的位置$i$就可以在$O(logN)$的时间复杂度内解决上述问题。

于是我们对于每个左端点求出对右端点区间内的最大值，并且使用一个五元组记录对应信息$(L,qL,qR,R,ans)$分别代表左端点，右端点取值区间$[qL,qR]$，产生答案的右端点，和对应答案，并且存入优先队列按照ans从大到小排序。我们每次从优先队列中取出一个元素，并且将值加到答案上，然后把这个五元组从R点分裂为两个较小的区间--$(L,qL,R-1,R_{new},ans_{new})$以及$(L,R+1,qR,R_{new},ans_{new})$并且塞入优先队列。显然更具这种方法就可以不重不漏的统计出前K大区间和。

线段树

#include <bits/stdc++.h>

const int MAXN = 2000005;

using namespace std;

int n,k,l,r,qL,qR,ql,qr;
long long sum[MAXN],ans; 

pair<long long,int>Max[MAXN],tmp; 

struct node{
    int L,qL,qR,R;
    long long ans;
    friend bool operator < (const node &A,const node &B){
        return A.ans < B.ans;
    }
    
}A,AL,AR;

priority_queue<node>Q;

inline int read()
{
    int x = 0,f = 1;char ch = getchar();
    while(ch < '0' || '9' < ch){if(ch == '-') f = -1;ch = getchar();}
    while('0' <=ch && ch <='9'){x = x * 10 + ch - '0';ch = getchar();}    
    return x*f;
}    

void update(int o,int L,int R){
    if(L == R){
        Max[o].first = sum[L];
        Max[o].second = L;
        return;
    }
    int M = L + R >> 1;
    update(o<<1,L,M);
    update(o<<1|1,M+1,R);
    Max[o] = max(Max[o<<1],Max[o<<1|1]);
}

void query(int o,int L,int R){
    if(ql <= L && R <= qr){
        tmp = max(tmp,Max[o]);
        return;
    }
    int M = L + R >> 1;
    if(ql <= M) query(o<<1,L,M);
    if(M < qr) query(o<<1|1,M+1,R);
}

inline void init()
{
    n = read();k = read();qL = read();qR = read();
    
    for(int i = 1;i <= n;i++) scanf("%lld",&sum[i]);
    
    for(int i = 1;i <= n;i++)
        sum[i] += sum[i-1];
    
    update(1,1,n);
    
    for(int i = 1;i <= n;i++)
    {
        A.L = i;
        if(i+qL-1 > n) break;
        ql = i+qL-1;
        qr = min(i+qR-1,n);
        tmp.first = -1000000000;tmp.second = 0;
        query(1,1,n);
        A.qL = ql;A.qR = qr;A.R = tmp.second;A.ans = tmp.first - sum[i-1];
        Q.push(A);
    }
    
}

int main()
{
    init();
    while(k--)
    {
        A = Q.top();Q.pop();
        ans += A.ans;
        ql = A.qL;qr = A.R - 1;
        if(ql <= qr) {
            tmp.first = -1000000000;tmp.second = 0;
            query(1,1,n);
            AL.L = A.L;AL.qL = ql;AL.qR = qr;AL.R = tmp.second;AL.ans = tmp.first - sum[A.L-1];
            Q.push(AL);    
        }
        ql = A.R + 1;qr = A.qR;
        if(ql <= qr){
            tmp.first = -1000000000;tmp.second = 0;
            query(1,1,n);
            AR.L = A.L;AR.qL = ql;AR.qR = qr;AR.R = tmp.second;AR.ans = tmp.first - sum[A.L-1];
            Q.push(AR);                    
        }
    }
    printf("%lld\n",ans);
    return 0;
}