比较裸的单调队列
先求前缀和,枚举所有结束位置1~n+k即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 200005
using namespace std; int ans,a[maxn],sum[maxn]; int main(){
int T,N,K;
scanf("%d",&T);
while(T--){
memset(sum,,sizeof sum);
scanf("%d%d",&N,&K);
for(int i=;i<=N;i++){
scanf("%d",&a[i]);
sum[i]=sum[i-]+a[i];
}
for(int i=N+;i<=N++K;i++){
a[i]=a[i-N];
sum[i]+=sum[i-]+a[i];
} ans=-;
int ansl,ansr,l=,r=,q[maxn];//单调队列求长度为k的区间中的最小值
q[]=;sum[]=;
for(int i=;i<=N+K;i++){
while(l<=r && q[l]<i-K)l++;
if(ans<sum[i]-sum[q[l]]){
ans=sum[i]-sum[q[l]];
ansl=q[l]+,ansr=i>N?i-N:i;
}
while(l<=r && sum[q[r]]>=sum[i]) r--;
q[++r]=i;
}
printf("%d %d %d\n",ans,ansl,ansr);
}
return ;
}