BZOJ 2006: [NOI2010]超级钢琴（ST表+优先队列）

题目描述

传送门

题目描述：给你一个长度为N的序列（N<=500,000），求长度在[L,R]中的前K（K<=500,000）大的连续子序列的和，其中-1000<=Ai<=1000。

---

思路

本来想写一道水题提升信心，结果没开long long调一年！

枚举一段连续子序列的末尾，用ST表可以求出长度在[L,R]中的和最大的答案与开头的位置。这相当于找满足条件的最小的sum[y]。

然后我们考虑如何取k个。好像可以开一个优先队列，将每个点为末尾的答案放进去，然后弹出前k大。但这样明显是错的。

对于同一个x，我们将最优的y放进去了，但不保证没有一个z也能贡献答案。于是我们弹出[l,r]后还要加入[l,y-1]和[y+1,r]（相当于把区间断开）。这是为了保证不取重复的答案。其中l和r是合法的开头的范围。

于是我们在优先队列里维护l,r,x,y四个元素。

时间复杂度O(nlogn+klogn)。注意别忘了y可以等于0，所以0也要在倍增时计算。

---

代码

#include <bits/stdc++.h>
#define maxn 500010
#define maxl 21

using namespace std;

int n, k, L, R;
long long ans;
int a[maxn], sum[maxn], f[maxl][maxn], g[maxl][maxn], Lg[maxn];

struct XJZ{
    int x, pos;
    int l, r;
    XJZ() {}
    XJZ(int _x, int _pos, int _l, int _r){
        x = _x;
        pos = _pos;
        l = _l;
        r = _r;
    }
    bool operator < (const XJZ& OTHER) const{
        return sum[x]-sum[pos] < sum[OTHER.x]-sum[OTHER.pos];
    }
};

priority_queue <XJZ> que;

void Da(){

    Lg[1] = 0;
    for(int i = 2; i <= n+1; i++)  Lg[i] = Lg[i>>1] + 1;

    for(int i = 0; i <= n; i++)  f[0][i] = sum[i], g[0][i] = i;
    for(int i = 1; i <= Lg[n+1]; i++)
        for(int j = 0; j <= n-(1<<i)+1; j++){
            if(f[i-1][j] < f[i-1][j+(1<<(i-1))]){
                f[i][j] = f[i-1][j];
                g[i][j] = g[i-1][j];
            }
            else{
                f[i][j] = f[i-1][j+(1<<(i-1))];
                g[i][j] = g[i-1][j+(1<<(i-1))];
            }
        }
}

void Push(int x, int l, int r){
    if(l > r)  return;
    int t = Lg[r-l+1], pos;
    if(f[t][l] < f[t][r-(1<<t)+1])  pos = g[t][l];
    else  pos = g[t][r-(1<<t)+1];
    que.push(XJZ(x, pos, l, r));
}

int main(){

    scanf("%d%d%d%d", &n, &k, &L, &R);

    sum[0] = 0;
    for(int i = 1; i <= n; i++){  
        scanf("%d", &a[i]);
        sum[i] = sum[i-1] + a[i];
    }

    Da();

    for(int i = 1; i <= n; i++){
        int l = max(i-R, 0), r = i-L;
        Push(i, l, r);
    }

    for(int i = 1; i <= k; i++){
        XJZ temp = que.top();  que.pop();
        ans += (long long)(sum[temp.x] - sum[temp.pos]);
        Push(temp.x, temp.l, temp.pos-1);
        Push(temp.x, temp.pos+1, temp.r);
    }

    printf("%lld\n", ans);

    return 0;
}

---