單調(diào)棧 & 單調(diào)隊(duì)列

如果一個(gè)人比你小，還比你強(qiáng)，那你就永遠(yuǎn)打不過他了。——單調(diào)隊(duì)列

經(jīng)過痛苦的折磨，我終于，把單調(diào)棧和單調(diào)隊(duì)列學(xué)會(huì)并理解了，但做的題還比較簡(jiǎn)單。

單調(diào)棧

顧名思義，就是維護(hù)一個(gè)具有單調(diào)性的棧，用于解決求序列中第 \(i\) 個(gè)數(shù)右邊第一個(gè)大于它的數(shù)（或者其下標(biāo)），當(dāng)然還有右邊第一個(gè)小于它的，左邊第一個(gè)大于它的，右邊第一個(gè)小于它的，此類問題。

luogu P5788 【模板】單調(diào)棧

求第 \(i\) 個(gè)數(shù)右邊第一個(gè)大于它的數(shù)（或者下標(biāo)），就要維護(hù)一個(gè)從棧頂至棧底 單調(diào)遞增 的棧（注意，為了方便，一般棧中存的是下標(biāo)），即棧頂是最小的數(shù)，當(dāng)遍歷到 \(i\) 并要加入 \(a_i\) 時(shí)，如果單調(diào)性將被破壞，就要彈棧，直到棧空或者棧頂元素所對(duì)應(yīng)的數(shù)（因?yàn)闂Ｖ写娴氖窍聵?biāo)，所以是以該元素為下標(biāo)所對(duì)應(yīng)的數(shù)）大于 \(a_i\) 時(shí)，停止彈棧，并把下標(biāo) \(i\) 壓入棧，而那些彈出的下標(biāo)，開一個(gè) \(r_i\) 數(shù)組，讓彈出的每個(gè)元素的 \(r\) 等于 \(i\)。最后，輸出的 \(r_i\) 就是第 \(i\) 個(gè)數(shù)右邊第一個(gè)大于它的數(shù)的下標(biāo)。

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+5;
int n,a[N],f[N],st[N],top;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		while(top&&a[st[top]]<a[i]) f[st[top--]]=i;
		st[++top]=i;
	}
	for(int i=1;i<=n;i++) cout<<f[i]<<" ";
	return 0;
}

接著是一些練習(xí)題：

luogu B3666 求數(shù)列所有后綴最大值的位置

本題只需利用異或特性，在彈出每個(gè)元素時(shí)，用 \(ans\) 異或該元素，然后輸出 \(ans\) 即可

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=1e6+5;
unsigned long long a[N],st[N];
int n,top,ans;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		while(top&&a[st[top]]<=a[i]) ans^=st[top],top--;
		st[++top]=i;
		ans^=i;
		cout<<ans<<endl;
	}
	return 0;
}

luogu P6503 [COCI 2010/2011 #3] DIFERENCIJA

給出一個(gè)長(zhǎng)度為 \(n\) 的序列 \(a_i\)，求出下列式子的值：

\[\sum_{i=1}^{n} \sum_{j=i}^{n} (\max_{i\le k\le j} a_k-\min_{i\le k\le j} a_k) \]

其中 \(2 \le n \le 3e5\)，\(1 \le a_i \le 1e8\)。

不難想到 \(O(n^2)\) 的暴力做法，這里不過多贅述。

考慮另一種思路：

\[\sum_{i=1}^{n} \sum_{j=i}^{n} (\max_{i\le k\le j} a_k-\min_{i\le k\le j} a_k) =\sum_{i=1}^{n} \sum_{j=i}^{n} \max_{i\le k\le j} a_k -\sum_{i=1}^{n} \sum_{j=i}^{n} \min_{i\le k\le j} a_k \]

拆成最大值和最小值兩部分的

一個(gè)數(shù) \(a_i\) （先考慮最大值）對(duì)最后的答案有貢獻(xiàn)，當(dāng)且僅當(dāng)其在一個(gè)區(qū)間 \([L,R]\) 中是最大的數(shù)，其貢獻(xiàn)就是最大的滿足這個(gè)條件的區(qū)間的 \([L,R]\) 的長(zhǎng)度乘它這個(gè)數(shù)，即：\((R-L+1)*a_i\)，所以我們要求的就是每個(gè) \(i\) 所對(duì)應(yīng)的 \([L,R]\)，用單調(diào)棧正反分別跑一次，分別求出每個(gè) \(R\)，\(L\)。最小值部分的貢獻(xiàn)也同理。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
int n,t1,t2,a[N];
ll l[2][N],r[2][N],s1[N],s2[N],ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		r[0][i]=r[1][i]=n;
		while(t1&&a[s1[t1]]<=a[i]) r[0][s1[t1]]=i-1,t1--;
		while(t2&&a[s2[t2]]>=a[i]) r[1][s2[t2]]=i-1,t2--;
		s1[++t1]=i;
		s2[++t2]=i;
	}
	t1=t2=0;
	for(int i=n;i;i--){
		l[0][i]=l[1][i]=1;
		while(t1&&a[s1[t1]]<a[i]) l[0][s1[t1]]=i+1,t1--;
		while(t2&&a[s2[t2]]>a[i]) l[1][s2[t2]]=i+1,t2--;
		s1[++t1]=i;
		s2[++t2]=i;
	}
	for(int i=1;i<=n;i++){
		ans+=1ll*a[i]*((i-l[0][i]+1)*(r[0][i]-i+1)-(r[1][i]-i+1)*(i-l[1][i]+1));
	}
	cout<<ans;
	return 0;
}

luogu P2422 良好的感覺

這題依舊一樣，仍然用單調(diào)棧求出每個(gè) \(i\) 所能到達(dá)的最大的 \([L,R]\)，滿足 \(a_i \le a_j\) \((i,j∈[L,R])\) 即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,l[N],r[N];
ll a[N],sum[N],st[N],top,ans;
int main(){
	cin>>n;
	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(top&&a[st[top]]>=a[i]) top--;
		l[i]=st[top];
		st[++top]=i;
	}
	top=0;
	st[top]=n+1;
	for(int i=n;i>0;i--){
		while(top&&a[st[top]]>=a[i]) top--;
		r[i]=st[top]-1;
		st[++top]=i;
	}
	for(int i=1;i<=n;i++) ans=max(ans,(sum[r[i]]-sum[l[i]])*a[i]);
	cout<<ans;
	return 0;
}

單調(diào)隊(duì)列

單調(diào)隊(duì)列解決的是求某一 滑動(dòng)窗口 的區(qū)間最值問題，雖然叫單調(diào)隊(duì)列，但事實(shí)上是基于雙端隊(duì)列實(shí)現(xiàn)的，我一般喜歡用手寫的雙端隊(duì)列，當(dāng)然，\(STL\) 有雙端隊(duì)列容器 \(deque\)，但我覺得，像這種線性的數(shù)據(jù)結(jié)構(gòu)自己手寫就好了（但是像優(yōu)先隊(duì)列，\(map\) 和 \(set\) 這種容器肯定要用 \(STL\)，應(yīng)該沒人想要賽時(shí)手寫這玩意吧。。。）

好了，說回正題，考慮怎么維護(hù)單調(diào)隊(duì)列？以求長(zhǎng)度為 \(L\) 的區(qū)間最小值為例：

維護(hù)一個(gè)由隊(duì)頭到隊(duì)尾 嚴(yán)格單調(diào)遞增 的雙端隊(duì)列，那么隊(duì)頭就是最小值（注意，雙端隊(duì)列里存的一般還是下標(biāo)，這有利于后面維護(hù)長(zhǎng)度 \(L\)，并且把雙端隊(duì)列簡(jiǎn)稱為隊(duì)列）

兩種操作：

1.當(dāng)加入的數(shù) \(a_i\) 會(huì)破壞隊(duì)列的單調(diào)性，即 \(a_i\) 大于等于隊(duì)尾元素所對(duì)應(yīng)的數(shù)時(shí)，彈出隊(duì)尾，直到隊(duì)列為空或者滿足單調(diào)性

2.當(dāng)隊(duì)首的元素已經(jīng)超出了滑動(dòng)窗口最左段，彈出隊(duì)首

對(duì)于每個(gè)下標(biāo) \(i\)，每次進(jìn)行完操作 \(2\) 后就把隊(duì)首的最值更新 \(i\) 的答案，然后把 \(i\) 的答案通過操作 \(1\) 入隊(duì)（當(dāng)然還是入的下標(biāo)）

luogu P1886 滑動(dòng)窗口 /【模板】單調(diào)隊(duì)列

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,k,a[N],q[N],hd=1,tl;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		while(hd<=tl&&a[q[tl]]>=a[i]) tl--;
		q[++tl]=i;
		while(hd<=tl&&q[hd]<=i-k) hd++;
		if(i>=k) cout<<a[q[hd]]<<" ";
	}
	cout<<endl;
	hd=1,tl=0;
	for(int i=1;i<=n;i++){
		while(hd<=tl&&a[q[tl]]<=a[i]) tl--;
		q[++tl]=i;
		while(hd<=tl&&q[hd]<=i-k) hd++;
		if(i>=k) cout<<a[q[hd]]<<" ";
	}
	return 0;
}

luogu B3667 求區(qū)間所有后綴最大值的位置

披著羊皮的板題

代碼：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=1e6+5;
int n,k,l=1,r,q[N];
unsigned long long a[N];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
        cin>>a[i];
        while(l<=r&&q[l]+k<=i) l++;//注意本題維護(hù)滑動(dòng)窗口的邊界，要算上當(dāng)前下標(biāo)i,所以要帶等號(hào)
		while(l<=r&&a[q[r]]<=a[i]) r--;
		q[++r]=i;
		if(i>=k) cout<<r-l+1<<endl;
	}
	return 0;
}

單調(diào)隊(duì)列一般是用于優(yōu)化的，例如多重背包，\(DP\) 等

luogu P1776 寶物篩選（多重背包單調(diào)隊(duì)列優(yōu)化）

#include<bits/stdc++.h>
using namespace std;
const int N=105,M=1e5+5;
int n,m,v,w,s,f[M],l,r,q[M],num[M];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w>>v>>s;
        int len=min(s,m/v);
        for(int b=0;b<v;b++){
            l=1,r=0;
            for(int y=0;y<=(m-b)/v;y++){
                int tmp=f[b+y*v]-y*w;
                while(l<=r&&q[r]<=tmp) r--;
                q[++r]=tmp;
                num[r]=y;
                while(l<=r&&num[l]<y-len) l++;
                f[b+y*v]=max(f[b+y*v],q[l]+y*w);
            }
        }
    }
    cout<<f[m];
    return 0;
}

luogu P2627 [USACO11OPEN] Mowing the Lawn G

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,m,l=1,r;
ll a[N],f[N][2],sum[N],q[N];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
		f[i][0]=max(f[i-1][0],f[i-1][1]);
		while(l<=r&&q[l]<i-m) l++;
		if(i<=m) f[i][1]=sum[i];
		else f[i][1]=f[q[l]][0]-sum[q[l]]+sum[i];
		while(l<=r&&f[q[r]][0]-sum[q[r]]<=f[i][0]-sum[i]) r--;
		q[++r]=i;
	}
	cout<<max(f[n][0],f[n][1]);
	return 0;
}

目前先到這里，11月會(huì)繼續(xù)更新的，也會(huì)把上面的解釋補(bǔ)充一下

posted @ 2025-10-29 08:43 czh（抽紙盒）閱讀(4) 評(píng)論(0) 收藏舉報(bào)

刷新頁(yè)面返回頂部

czh-ak-NOI

單調(diào)棧 & 單調(diào)隊(duì)列

單調(diào)棧 & 單調(diào)隊(duì)列

單調(diào)棧

luogu P5788 【模板】單調(diào)棧

luogu B3666 求數(shù)列所有后綴最大值的位置

luogu P6503 [COCI 2010/2011 #3] DIFERENCIJA

luogu P2422 良好的感覺

單調(diào)隊(duì)列

luogu P1886 滑動(dòng)窗口 /【模板】單調(diào)隊(duì)列

luogu B3667 求區(qū)間所有后綴最大值的位置

luogu P1776 寶物篩選（多重背包單調(diào)隊(duì)列優(yōu)化）

luogu P2627 [USACO11OPEN] Mowing the Lawn G

公告