BZOJ2006 - [Noi2010]超级钢琴

2017/03/18

我好菜啊 _(:з」∠)_

本周智商下线。。。写啥都写不出来,学校数学课卡题卡到爆炸,考试抄错答题卡。呜呜呜

题目

给一个序列求长度在 [L, R] 间的前 k 大子段和。

代码

用堆维护一个三元组 (B, L, R) 表示从 B 开始,到 [L, R] 任意位置结束的最优情况。
然后每次贪心如果最优答案的终点在位置 M ,就先 pop 当前三元组,插入 (B, L, M-1) 和 (B, M+1, R)。

如何求出 (B, L, R) 这个三元组的最大和呢?
先求出前缀和,那么最优的位置可以通过 ST 表在前缀和上 RMQ 出来。
最终的答案就是前缀和上 Pre[M] - Pre[B - 1]

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#ifdef LCYTEST
#define logf(fmt, arg...) printf("[LOG] "fmt, ##arg)
#else
#define logf(fmt, arg...) { ; }
#endif
using namespace std;
const int MAX_N = int(2E6);
typedef long long LL;

struct seg {
    int B, L, R;
    pair<LL, int> S;
    
    seg(int B, int L, int R, pair<LL, int> S) :
        B(B), L(L), R(R), S(S) { }
    
    friend bool operator<(const seg &lhs, const seg &rhs) {
        return lhs.S.first < rhs.S.first;
    }
};

int N, K, L, R;
int Src[MAX_N];
LL Pre[MAX_N]; // Pre[n] repr [1, n]
LL Max[20][MAX_N];
int Maxid[20][MAX_N];
int Log2[MAX_N];

void make_st() {
    Log2[0] = -1;
    for(int i=1;i<=N;i++) {
        Log2[i] = Log2[i>>1] + 1;
    }
    
    for(int i=1;i<=N;i++) {
        Max[0][i] = Pre[i];
        Maxid[0][i] = i;
    }
    
    for(int j=1;j<=Log2[N];j++) {
        int c = (1 << j) - 1;
        for(int i=1;i+c<=N;i++) {
            Max[j][i] = max(Max[j-1][i], Max[j-1][i + (1 << (j-1))]);
            Maxid[j][i] = (Max[j][i] == Max[j-1][i] ?
                Maxid[j-1][i] : Maxid[j-1][i + (1 << (j-1))]);
        }
    }
}

pair<LL, int> query(int L, int R) { // Query on [L, R]
    int k = Log2[R - L + 1];
    LL a = Max[k][L];
    LL b = Max[k][R - (1 << k) + 1];
    return make_pair(max(a, b), (a>=b?Maxid[k][L]:Maxid[k][R-(1<<k)+1]));
}

LL work() {
    priority_queue<seg> PQ;

    for(int i=1;i<=N;i++) {
        if(i+L-1 <= N) {
            int t = min(N, i+R-1);
            pair<LL, int> tmp = query(i+L-1, t);
            tmp.first -= Pre[i-1];
            PQ.push(seg(i, i+L-1, t, tmp));
        }
    }
    
    int k = K;
    LL ret = 0LL;
    while(!PQ.empty() && k) {
        seg cur = PQ.top(); PQ.pop();
        
        ret += cur.S.first;
        
        int M = cur.S.second;
        
        logf("Sel [%d, %d] = %d\n", cur.B, cur.S.second, cur.S.first);
        
        if(cur.L < M) {
            pair<LL, int> tmp = query(cur.L, M-1);
            tmp.first -= Pre[cur.B-1];
            logf("Ins [%d, (%d %d)] = %d\n", cur.B, cur.L, M-1, tmp.first);
            PQ.push(seg(cur.B, cur.L, M-1, tmp));
        }
        
        if(M < cur.R) {
            pair<LL, int> tmp = query(M+1, cur.R);
            tmp.first -= Pre[cur.B-1];
            logf("Ins [%d, (%d %d)] = %d\n", cur.B, M+1, R, tmp.first);
            PQ.push(seg(cur.B, M+1, cur.R, tmp));
        }
        
        k--;
    }
    
    return ret;
}

int main() {
    scanf("%d %d %d %d", &N, &K, &L, &R);
    
    for(int i=1;i<=N;i++) {
        scanf("%d", &Src[i]);
        Pre[i] = Pre[i-1] + Src[i];
    }
    
    make_st();
    
    printf("%lld\n", work());
}