这一道题显然是一道 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;
}

差不多就是这样了……

分类: 文章

Qiuly

井戸の底の空にはまだかすかな希望の光がある……

4 条评论

XZYQvQ · 2018年12月16日 8:10 下午

emmm 大佬您是哪个学校的呀 QAQ

另外您能加我 QQ 吗?您的那个 649****51QQ 看起来是您的家长的吧 Orz

    Qiuly · 2018年12月17日 4:50 下午

    可以呀,但我不是大佬,我是来自 CSSYZ 信息学集训队的一枚蒟蒻 QAQ

      XZYQvQ · 2018年12月17日 6:27 下午

      集训队员 Orz %%%%%

    Qiuly · 2018年12月17日 4:52 下午

    您才是大佬。

    您还给我讲过【逛公园】这道题呢 (可是我貌似没打)

发表评论

电子邮件地址不会被公开。 必填项已用*标注