确认右端点后，即可确认左端点的范围，则能确认该右端点能取到的最大值（用前缀和维护sum=s[i]-s[j],s[i]确认，则用ST表维护s[j]最小值）
用优先队列维护，每次取最大值，再将以该右端点为右端点的左右两段区间最值分别放入队列中
#include<cstdio>
#include<cctype>
#include<queue>
#define maxn 500002
#define mp(a,b,c,d) make_pair(make_pair(a,b),make_pair(c,d))
using namespace std;
typedef pair<
int,
int>
data;
priority_queue<pair<data,data> >
q;
int n,m,l,r,logg[maxn],f[maxn][
20],s[maxn],v[maxn];
long long ans;
inline void read(
int &
x){
char ch=getchar();x=
0;
int f=
1;
while(!isdigit(ch)){
if(ch==
'-')f=-
1;ch=
getchar();}
while(isdigit(ch)){x=(x<<
1)+(x<<
3)+ch-
'0';ch=
getchar();}
x*=
f;
}
inline int mn(
int a,
int b){
return s[a]<s[b]?
a:b;}
inline int query(
int a,
int b){
if(a>b)
return -
1;
int k=logg[b-a+
1];
return mn(f[a][k],f[b-(
1<<k)+
1][k]);}
int main(){
int c,d,x,a,b,y;
read(n);read(m);read(l);read(r);
for(
int i=
2;i<=n;i++)logg[i]=logg[i>>
1]+
1;
for(
int i=
1;i<=n;i++){f[i][
0]=i;read(v[i]);s[i]=v[i]+s[i-
1];}
for(
int j=
1;(
1<<j)<=n;j++
)
for(
int i=
0;i+(
1<<j)<=n;i++
)
f[i][j]=mn(f[i][j-
1],f[i+(
1<<j-
1)][j-
1]);
for(
int i=l;i<=n;i++)q.push(mp(s[i]-s[query(max(i-r,
0),i-l)],i,max(i-r,
0),i-
l));
for(
int i=
1;i<=m;i++
){
data t1=q.top().first,t2=
q.top().second;
ans+=t1.first;x=t1.second;a=t2.first;b=t2.second;y=
query(a,b);q.pop();
c=query(a,y-
1);d=query(y+
1,b);
if(c!=-
1)q.push(mp(s[x]-s[c],x,a,y-
1));
if(d!=-
1)q.push(mp(s[x]-s[d],x,y+
1,b));
}
printf("%lld",ans);
return 0;
}
转载于:https://www.cnblogs.com/MikuKnight/p/9159704.html
