HDU 3415 单调队列

求长度不大于\(k\)的最大子段和

求前缀和，枚举答案的右端点，对于每个右端点，求以该点为右端点，长度为\(k\)的区间的最小值
用单调队列维护值单调递增的下标，对于每个右端点，若队首元素与当前位置的距离不满足要求，则出队，否则记录答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100010;
int a[maxn<<1],q[maxn<<1];
int main()
{
    int _,n,k;
    for(scanf("%d",&_);_;_--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)a[i+n]=a[i];
        n<<=1;
        for(int i=1;i<=n;i++)a[i]+=a[i-1];
        int l=0,r=2,ans=a[1],lans=1,rans=1;
        q[0]=0;
        q[1]=1;
        for(int i=2;i<=n;i++){
            while(l<r&&q[l]+k<i)l++;
            if(a[i]-a[q[l]]>ans){
                ans=a[i]-a[q[l]];
                lans=q[l]+1;
                rans=i;
            }
            while(l<r&&a[i]<a[q[r-1]])r--;
            q[r++]=i;
        }
        if(lans>n/2)lans-=n/2;
        if(rans>n/2)rans-=n/2;
        printf("%d %d %d\n",ans,lans,rans);
    }
    return 0;
}

HDU 3415 单调队列

原文：https://www.cnblogs.com/Zeronera/p/13583183.html