單調棧和單調佇列都是藉助單調性，及時排除不可能的決策，保持候選集合的高度有效性和秩序性。單調佇列尤其適合優化決策取值範圍的上、下界均單調變化，每個決策在候選集合中插入或刪除至多一側的問題。
利用單調佇列，我們可以捨去許多無用的狀態，來更快的找出最優解。
一般用單調佇列維護的都是根據題目而定，比如求 XX 最小值，那麼我們就要維護一個單調遞增的佇列，因為這樣隊頭的元素是始終最小的；反之求 XX 最大值，我們就要維護一個單調遞減的佇列，因為這樣隊頭元素始終是最大的。
持續更新題目中，約為三天
顯然最樸素的方法是直接暴力，但是 \(3\times 10^{5}\) 的資料範圍是不會讓我們 AC 的。
我們考慮利用單調佇列來優化一下複雜度。
首先我們看到求連續的一段的和，所以我們先預處理出字首和。
首先我們知道如果當前遍歷到的元素的下標減去佇列頭的元素是大於 \(m\) 的話，這個是不合法的，所以我們每到了一個點都要先把這些不合法的都給彈出去，然後在進行求解。
我們維護一個單調遞增的佇列，這樣我們的頭部元素保證是這個區域內最優的一塊，然後我們統計答案直接用當前點的字首和減去頭部第一個元素的下標對應的字首和就好了。
code:
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long
#define N 1000100
using namespace std;
int n,m,a[N],sum[N],q[N],h,t,ans=-INF;
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;i++)
{
while(h<=t&&i-q[h]>m)h++;
ans=max(ans,sum[i]-sum[q[h]]);
while(h<=t&&sum[q[t]]>=sum[i])t--;
q[++t]=i;
}
cout<<ans<<endl;
return 0;
}
我們設 \(f[i][j]\) 表示前 \(i\) 個人粉刷前 \(j\) 塊木板的最大花費。
我們對於每一個人，列舉每一塊木板，我們都有以下三種情況：
當前人不粉刷，f[i][j]=max(f[i-1][j],f[i-1][j])
當前人粉刷，但是不粉刷當前木板 f[i][j]=max(f[i][j-1],f[i][j])
當前人粉刷且粉刷當前木板、
第三種情況又分為兩種情況。
當前的 \(j<s_{i}\)，只能做左端點，因為必須包含 \(s_{i}\)，所以這個時候，我們維護一個以佇列裡的點為起點時花費最大的花費單調遞增的佇列，也就是說，我們佇列裡面是左端點，但是我們裡面單調遞增的，是未計算當前粉刷的區間時最大的花費。
當前點 \(j>=s_{i}\)，只能做右端點，這個時候我們判斷一下佇列裡的元素是否和當前點的最大長度不超過 \(l\)，然後我們進行計算，設我們從裡面取出的左端點為 \(k\)，則 f[i][j]=max(f[i][j],f[i-1][k]+(j-k)*p_{i})。
然後就得出答案了。
code:
#include<bits/stdc++.h>
#define N 100010
#define M 110
using namespace std;
int n,m,q[N],f[M][N];
struct sb{int l,p,s;}e[N];
inline int cmp(sb a,sb b){return a.s<b.s;}
signed main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)cin>>e[i].l>>e[i].p>>e[i].s;
sort(e+1,e+m+1,cmp);//按必須包含的木板s來從小到大排序
for(int i=1;i<=m;i++)//列舉每一個工匠
{
int h=0,t=0;//頭尾指標
for(int j=0;j<=n;j++)
{
f[i][j]=f[i-1][j];//當前工人不用
if(j)f[i][j]=max(f[i][j],f[i][j-1]);//當前木板不粉刷
int l=e[i].l,p=e[i].p,s=e[i].s;//區間最大長度，單位花費，必須包含的木板
if(h<=t&&q[h]<j-l)h++;//如果要是佇列裡最靠左的元素在當前的區間左邊，我們直接彈出
if(j>=s&&h<=t)//如果要是當前點大於s且佇列不空，那j就只能是區間右端點
{
int k=q[h];//取出隊頭元素
f[i][j]=max(f[i][j],f[i-1][k]+p*(j-k));//取max
}
if(j<s)//如果要是當前點不包含s就只能做左端點
{
while(h<=t&&f[i-1][q[t]]-q[t]*p<=f[i-1][j]-j*p)t--;//如果以當前的尾部元素為起點的話不如以當前點為起點更優就彈出，維護佇列內的起點的價值單調遞增
q[++t]=j;//入列
}
}
}
cout<<f[m][n]<<endl;//輸出m個工匠粉刷n個木板的最大收益
return 0;
}
我們觀察題目，發現如果要是從一點點轉移到一個區間是不好轉移的，所以我們轉化一下問題，變為當前點由那些點轉移過來，這樣我們就可以由已經處理好的問題來處理當前的問題了。
我們手模一下可以發現，點 \(i\) 只能由 \([i-R,i-L]\) 轉移而來，所以我們直接用一個單調佇列來維護裡面的 \(f[k]\) 單調遞減，也就是說，我們每次到了點 \(i\) 都把當前最大能轉移到 \(i\) 的點給放入佇列，然後維護一個單調遞減的佇列，這樣讓我們的頭部元素始終是最優的，我們就可以通過頭部元素轉移到當前點；當然我們也要判斷是否在這個區間內，把不合法的先彈出去。
code:
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long
#define N 1000100
using namespace std;
int n,L,R,a[N],f[N],q[N],h,t=-1,ans=-INF;
signed main()
{
cin>>n>>L>>R;
for(int i=0;i<=n;i++)cin>>a[i];
memset(f,-127,sizeof f);
f[0]=0;
for(int i=L;i<=n;i++)
{
while(h<=t&&f[q[t]]<=f[i-L])t--;
q[++t]=i-L;
while(h<=t&&q[h]<i-R)h++;
f[i]=f[q[h]]+a[i];
// for(int j=h;j<=t;j++)cout<<f[q[j]]<<" ";cout<<endl;
if(i>n-R)ans=max(ans,f[i]);
}
cout<<ans<<endl;
return 0;
}