超级钢琴

有 \(n\) 个音符，编号从 \(1\) 到 \(n\) 。第 \(i\) 个音符的美妙度为 \(A_i\) 。

我们要找到 \(k\) 段不同超级和弦组成的乐曲，每段乐曲的连续音符个数 \(x\) 满足 \(L \le x \le R\) ， 求乐曲美妙度的最大值。

注：当且仅当这两个超级和弦所包含的音符集合是相同的。

Solution

我们定义 \(f_{idx,l,r}\) 为左端点为 \(idx\) ，右端点在 \(L \le right \le R\) 区间内的最大值。

我们可以先求出对于每个左端点 \(idx\) ，长度为 \(L \le x \le R\) 中的超级和弦组成的乐曲中的最大值。求出之后我们可以知道，所有符合条件的乐曲美妙度的最大值一定是上面求的所有值中的最大值。 假设 \(f_{idx,l,r}\) 是我们当前求得的最大值，并且取得最大值的右端点为 \(right\)

那么以 \(idx\) 为左端点的区间就可以分裂为 \(f_{idx,l, right - 1}\) 和 \(f_{idx, right + 1, r}\) ，即是对于左端点 \(idx\) 我们把右端点 \(right\) 这个可能性删去。

那么我们考虑维护一个优先队列，先把所有左端点的可能性放进堆中，每次取出堆顶，然后把堆顶分裂，继续加入堆中，当我们取出 k 次之后，就得到了答案。

现在有个问题是怎么求出对于 \(f_{idx,l,r}\) 取得最大值的右端点 \(right\) ，本题的查询是离线，那么我们可以考虑用 ST表 预处理出 \([l,r]\) 区间内的前缀和的最大值的下标。 这样我们既可以求得 \(right\) 又可以求得 最大值 \(s[right] - s[idx - 1]\) 。

CODE

const int N = 5e5 + 10;

int n, k, l, r;
int a[N], s[N];
int f[N][20];

inline void init() {
    for(int i = 1; i <= n; i ++ ) f[i][0] = i;
    for(int j = 1; (1 << j) <= n; j ++ )
        for(int i = 1; i + (1 << j) - 1 <= n; i ++  ){
            int x = f[i][j - 1], y = f[i + (1 << (j - 1))][j - 1];
            f[i][j] = s[x] >= s[y] ? x : y;
        }
}

inline int query(int l, int r ) {
    int k = log(r - l + 1) / log(2);
    int x = f[l][k], y = f[r - (1 << k) + 1][k];
    return s[x] >= s[y] ? x : y;
}


struct node {
    int i, l, r, nw;
    bool operator < (const node &t) const {
        if(t.nw != nw) 
            return t.nw > nw;
        if(t.i != i) 
            return t.i > i;
        if(t.l != l) 
            return t.l > l;
        return t.r > r;
    }
};
priority_queue<node> q;
inline void solve() {
    scanf("%d%d%d%d", &n, &k, &l, &r);
    for(int i = 1; i <= n; i ++ ) { scanf("%d", &a[i]); s[i] = s[i - 1] + a[i]; }
    init();
    node res;
    for(int i = 1; i <= n; i ++ ) {
        res.i = i; res.l = i + l - 1, res.r = min(n, i + r - 1);
        if(res.l > n) break;
        res.nw = s[query(res.l, min(n, res.r))] - s[i - 1];
        q.push(res);
    }
    LL ans = 0;
    int cnt = 0;
    while(q.size()) {
        auto t = q.top(); q.pop();
        ans += t.nw;
        cnt ++;
        if(cnt >= k) break;
        int p = query(t.l, t.r);
        if(p > t.l) {
            q.push({t.i, t.l, p - 1, s[query(t.l, min(n, p - 1))] - s[t.i - 1]});
        } 
        if(p < t.r) {
            q.push({t.i, p + 1, t.r, s[query(p + 1, min(n, t.r))] - s[t.i - 1]});
        }
    }
    printf("%lld\n", ans);
}