琪露诺 双端队列优化转移方程

#include<cstdio>
#include<cstring>
#include<deque>
#include<algorithm>
using namespace std;
const int maxn=200100;
struct node
{
    int val;//DP最大值 
    int num;//
};

int n,a[maxn],l,r;
int dp[maxn];
deque <node> s;
int main()
{
    scanf("%d%d%d",&n,&l,&r);
    for(int i=0;i<=n;i++)
    {
        scanf("%d",a+i);
    }
    int tail=0;dp[tail]=0;
    node x;
    for(int i=l;i<=n;i++)//从0开始转移向l处 
    {
        while(s.size()&&dp[tail]>=s.back().val)
        {
            s.pop_back();
        }//无用值弹出 
        x.num=tail;x.val=dp[tail];
        s.push_back(x);//加入新值 
        if(tail-s.front().num>=(r-l+1)) s.pop_front();//队列的长度 
        dp[i]=s.front().val+a[i];//此时队列最前面的是前面能到达i的最大值 
        tail++;
    }
    int ans=-maxn;
    for(int i=n-r+1;i<=n;i++)
    {
        ans=max(ans,dp[i]);
    }
    printf("%d",ans);
    return 0;
}