【题解】[NOI2010] 超级钢琴 RMQ+优先队列 bzoj2006/洛谷 P2048

这一道题显然是一道 RMQ 的题目，用一个三元素组 $（o，l，r）$表示：左端点为 o，右端点在 l 到 r 的区间内的最大子段，元素组用堆维护。

对于每个和弦的值，用前缀和在 $O(1)$的时间复杂度求出。

$ans$累加这个三元组的贡献。由于 $t$已经被选中，对于这个 $o$，$t$已经不能重复选中，但最优解还可能存在于 $t$左右的两端区间中，所以提取出 $(o, l, r)$之后，为了避免重复且不丧失其他较优解，我们仍然要把 $(o, l, t – 1),(o, t + 1, r)$扔回堆里面去。还要避免重复或错误，即 $l = t$或 $r = t$的情况要进行特判。

对于 $t$的位置，我们直接用 ST 表预处理出即可。

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define Macth
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
const int N=500005,Log=20;
ll f[N][Log],sum[N];
template <typename Tp> inline void read(Tp &x){
    x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
}
namespace RMQ{//ST 表求区间最优位置 (貌似在本题中是这样)
    inline void make(int n){
        for(register int i=1;i<=n;++i)f[i][0]=i;
        for(register int j=1;(1<<j)<=n;++j)
           for(register 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]=sum[x]>sum[y]?x:y;//取更优的位置
        }return;
    }
    inline int query(int l,int r){
        int k=log2(r-l+1);
        int x=f[l][k],y=f[r-(1<<k)+1][k];
        return sum[x]>sum[y]?x:y;
    }
}
int n,k,L,R;
struct Queue{
    int l,r,o,t;//t 就是最优的位置
    Queue(){}
    Queue(int o,int l,int r):o(o),l(l),r(r),t(RMQ::query(l,r)){}//t: 取个 l 至 r 区间的最优值
    bool operator < (Queue a)const{//重载运算符
        return sum[a.t]-sum[a.o-1]<sum[t]-sum[o-1];
    }
}A;
std::priority_queue<Queue> q;
int main(){
    scanf("%d%d%d%d",&n,&k,&L,&R);
    for(register int i=1;i<=n;++i){
        scanf("%lld",&sum[i]);sum[i]+=sum[i-1];
    }RMQ::make(n);ll ans=0;
    for(register int i=1;i<=n;++i){ 
       if(i+L-1<=n)q.push(Queue(i,i+L-1,min(i+R-1,n)));
    }while(k--){
        A=q.top();q.pop();
        ans+=sum[A.t]-sum[A.o-1];//更新 ans
        if(A.l!=A.t)q.push(Queue(A.o,A.l,A.t-1));
        if(A.r!=A.t)q.push(Queue(A.o,A.t+1,A.r));
    }printf("%lld\n",ans);
    return 0;
}

差不多就是这样了……