专栏文章

[NOI2010] 超级钢琴 题解

CChaniaq_awa
P2048题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miptyyz4
此快照首次捕获于
2025/12/03 17:54
3 个月前
此快照最后确认于
2025/12/03 17:54
3 个月前
查看原文

写在前面

又是为数不多我自己切出来的紫题...思路不是很难，如果没做过P1631可以先做做，是这题单调队列部分性质的基础，我认为最难的还是单调队列部分

整体思路

看到题面连续的一段那我们会想到前缀和，所以这里我们联系前缀和很容易会想到优先队列。我们确定每个左端点后需要找到最优解的右端点，找最优解的右端点的时候我们用 stst 表优化。

ST表

我们先求出前缀和。 这时我们思考，如果枚举了每个左端点，我们该如何找右端点让答案更大？
这里先给出前缀和表达式 ： ans=sum[右端点]−sum[左端点−1]ans = sum[右端点] - sum[左端点-1]
因为我们是枚举的左端点，所以 sum[左端点−1] sum[左端点-1] 一定是确定的。那这时我们想让 ansans 更大我们应该怎样相信很显而易见了，就是增大 sum[右端点]sum[右端点] .
那我们已知st表是找任意区间内的最大值或最小值，而题目又限制了 L,RL,R 那么st表就是当前最好的选择。那么这样我们就得到了以每个 i(1<=i<=n)i { (1 <= i <= n)} 开头的最大值。

优先队列部分

明白st表的部分，相信这部分也不是很难了。 我们先回顾一下优先队列的作用:定义一个优先级，栈顶是优先级最高的元素，插入删除的复杂度都是 loglog 级别的。
我们现在已经通过自己的努力得到了 nn 个较大的区间。为什么是较大呢，这也是我们要使用优先队列的原因。如果一段区间的值很大，有一段区间的值很小。因为我们是按照左端点入队的，所以会产生这样的差异。那段区间值大的区间，就算不是那个最优的右端点，是次优的右端点。那么有可能会比区间值很小的区间值大。
所以我们按照区间值排序，每次出队。但是我们有可能像上面我说的一样遗漏方案。所以还是得把最优的去掉，然后在剩下的里面取最优的。也就是分成两部分。

具体实现

每一个待定区间我们可以把看成三元组，第一个是左端点，第二个是右端点的最小值，第三个是右端点的最大值。 剩下直接打板子就好了，具体看我代码。
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
const int LG = 20;
long long s[N];
int st[N][LG];
void init(int n) {
    for(int i=1; i<=n; ++i) st[i][0] = i;
    for(int j=1; (1<<j)<=n; ++j)
        for(int i=1; i+(1<<j)-1<=n; ++i) {
            int x = st[i][j-1], y = st[i+(1<<(j-1))][j-1];
            st[i][j] = s[x] > s[y] ? x : y;
        }
}

int qmax(int l, int r) {
    int k = log2(r-l+1);
    int x = st[l][k], y = st[r-(1<<k)+1][k];
    return s[x] > s[y] ? x : y;
}
struct E {
    int o,l,r,t;
};
bool operator < (const E& a, const E& b) {
    return (s[a.t]-s[a.o-1]) < (s[b.t]-s[b.o-1]);
}
priority_queue<E> pq;
int main() {
    int n,k,L,R;
    cin >> n >> k >> L >> R;
    
    for(int i=1; i<=n; ++i) {
        cin >> s[i];
        s[i] += s[i-1];
    }
    init(n);
    
    
    for(int i=1; i<=n; ++i) {
        int r = min(i + R - 1, n);
        if(i + L - 1 <= n) {
            E tmp;
            tmp.o = i;
            tmp.l = i+L-1;
            tmp.r = r;
            tmp.t = qmax(tmp.l, tmp.r); 
			// t是最大sum[t] 
            // 公式为sum[t] - sum[o - 1] 
            pq.push(tmp);
        }
    }
    
    long long ans=0;
    while(k--) {
        auto e = pq.top(); pq.pop();
        ans += s[e.t] - s[e.o-1];
        if(e.l < e.t) { 
            E tmp;
            tmp.o = e.o;
            tmp.l = e.l;
            tmp.r = e.t-1;
            tmp.t = qmax(tmp.l, tmp.r);
            pq.push(tmp);
        }
        if(e.t < e.r) {
            E tmp;
            tmp.o = e.o;
            tmp.l = e.t+1;
            tmp.r = e.r;
            tmp.t = qmax(tmp.l, tmp.r);
            pq.push(tmp);
        }
    }
    
    cout << ans;
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...