单调栈
title: 单调栈
categories:
- ICPC
tags:
- null
abbrlink: 16518a5d
date: 2023-08-27 00:00:00
从单调栈到笛卡尔树
功能1：单调栈可以在线性时间内为每个数找到序列中下一个比它的大的数，以及上一个比它大的数
https://vjudge.net/problem/POJ-2796单调栈基本功能代表作
poj的c++98首先对size函数不是O（1）的，然后还卡关了同步流的cin，关键数据范围才1e5,逆天毒瘤，耽误我40min，以后poj的题目先测试一下是不是卡常数。然后我不熟悉printf的输出longlong，应该用%lld
题意：给定一个数组，找到一个区间，使得 最大化 区间里的数的和$\times$区间最小值
Sol：直接单调栈维护每个数作为最小值能到的左右边界，然后O（n)枚举更新答案即可，前缀和优化一下。
int a[N];
ll s[N];
stack<int>pre;
stack<int>nxt;
//找到两侧第一个比它小的下标
int l[N];
int r[N];
void solve(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
for(int i=1;i<=n;i++){
while(!pre.empty()&&a[i]<=a[pre.top()])pre.pop();
if(!pre.empty())l[i]=pre.top()+1;
else l[i]=1;
pre.push(i);
}
for(int i=n;i>=1;i--){
while(!nxt.empty()&&a[i]<=a[nxt.top()])nxt.pop();
if(!nxt.empty())r[i]=nxt.top()-1;
else r[i]=n;
nxt.push(i);
}
// for(int i=1;i<=n;i++)cerr<<a[i]<<" ";
// cerr<<endl;
// for(int i=1;i<=n;i++)cerr<<l[i]<<" ";
// cerr<<endl;
// for(int i=1;i<=n;i++)cerr<<r[i]<<" ";
// cerr<<endl;
ll ans=-inf,ansl=0,ansr=0;
for(int i=1;i<=n;i++){
ll tmp=(s[r[i]]-s[l[i]-1])*a[i];
if(ans<=tmp){
ans=tmp;
ansl=l[i];
ansr=r[i];
}
}
printf("%lld\n",ans);
printf("%lld %lld",ansl,ansr);
}
基础题补充 POJ - 2559 && POJ - 3494 (单调栈) - _Carrot - 博客园 (cnblogs.com)
功能2：解决某些涉及到“两元素间所有元素均(不)大/小于这两者”的问题。
https://www.luogu.com.cn/problem/P1823
$n$ 个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人 $a$ 和 $b$，如果他们是相邻或他们之间没有人比 $a$ 或 $b$ 高，那么他们是可以互相看得见的。写一个程序计算出有多少对人可以互相看见。
Sol：考虑偏序关系，我们只向左看保证不重复。题目的意思是两个人之间没有高的障碍物，因为要相互看见，每次找到左边第一个比当前数大的数，中间的数删除。如果从头开始做这个过程，会发现保存的序列是单调递减的，只保留了关键点。答案的累加过程中。接下来是本题的一个处理难点，就是连续的相同的元素，我们考虑用pair在插入的时候记录出现了几次，保证元素的值在栈中唯一。
debug：1.每次要判是否存在左边第一个比当前数大的数，这个数也会对答案贡献。
2。要开longlong。
int a[N];
//stl的栈不好调试啊
//每次向左看能看到多少人，能看到第一个比a高的人结束，保证单调减的
//单调栈的储存的是看到当前位置的人，这是意义，但没用
//对于相同的身高如果删掉会导致后面数吃不到，连续相同的数会出现这种情况
//对于上一行的问题我们选择用pii记录当前这个数已经重复出现了几次，在插入的时候就储存信息
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
stack<pii>stk;
ll ans=0;
for(int i=1;i<=n;i++){
int cnt=0;
while(stk.size()&&a[stk.top().fs]<=a[i]){
int tmp=a[stk.top().fs];
if(tmp==a[i])cnt=stk.top().sec;
ans+=stk.top().sec;
stk.pop();
}
cnt++;
if(stk.size())ans++;//第一个比它大是能看到的
stk.push({i,cnt});
}
cout<<ans<<endl;
}
单调栈dp算法学习笔记(67): 单调栈 - 知乎 (zhihu.com)
https://codeforces.com/contest/1313/problem/C2
这题是 CF1313C1 的较难版本。这个版本中 $1 \leq n \leq 500000$。给定一个数组，每个位置填数，最大可以填到a[i]，给了一些限制，要求你最大化的填的数字总和。如果规范地表示，让我们把地编上一个编号从 $1$ 到 $n$。那么如果在第 $i$ 块地的摩天大厦有 $a_i$ 层，那么我们需要保证 $1 \le ans_i \le a_i$。另外，这里不可以有整数 $j$ 和 $k$ 满足 $j < i < k$ 并且 $ans_j > ans_i < ans_k$。第 $j, k$ 块地并不需要与第 $i$ 块地相邻。
Sol；好的dp往往需要先贪心才能出思路或有想法，需要先冷静分析。对于题目的限制条件我们为了避免出现极小值，最多只能有一次下降，所以一般情况是填的数字先单增再单减。
根据这个我们得到一个$O(n^2)$的做法，我们枚举最高点的位置，然后花费$O(n)$的代价去向左右递推本次数的和，这个递推是简单的。这个做法可以过掉c1版本。
int cal(int pos){
int up=a[pos];
int res=a[pos];
for(int i=pos-1;i>=1;i--){
up=min(up,a[i]);
res+=up;
}
up=a[pos];
for(int i=pos+1;i<=n;i++){
up=min(up,a[i]);
res+=up;
}
return res;
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int ans=0;
int id=0;
for(int i=1;i<=n;i++){
if(ans<cal(i)){
ans=cal(i);
id=i;
}
}
vector<int>f(n+1);
f[id]=a[id];
int up=a[id];
for(int i=id-1;i>=1;i--){
up=min(up,a[i]);
f[i]=up;
}
up=a[id];
for(int i=id+1;i<=n;i++){
up=min(up,a[i]);
f[i]=up;
}
for(int i=1;i<=n;i++)cout<<f[i]<<" ";
}
考虑如何优化这个dp？如果能够预处理递推的结果就好了，这样我们就可以$O(1)$计算了。我们考虑预处理
int a[N];
int dpl[N];
int dpr[N];
int l[N],r[N];
stack<int>pre,nxt;
//先预处理l[i],r[i]-->del,dpr
//最后o（n)枚举，o(1)计算更新
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
while(pre.size()&&a[i]<=a[pre.top()])pre.pop();
if(pre.empty())l[i]=1;
else l[i]=pre.top()+1;
pre.push(i);
}
for(int i=n;i>=1;i--){
while(nxt.size()&&a[i]<=a[nxt.top()])nxt.pop();
if(nxt.empty())r[i]=n;
else r[i]=nxt.top()-1;
nxt.push(i);
}
for(int i=1;i<=n;i++){
dpl[i]=dpl[l[i]-1]+(i-l[i]+1)*a[i];
}
for(int i=n;i>=1;i--){
dpr[i]=dpr[r[i]+1]+(r[i]-i+1)*a[i];
}
int ans=0;int id=0;
for(int i=1;i<=n;i++){
if(ans<dpl[i]+dpr[i]-a[i]){
ans=dpl[i]+dpr[i]-a[i];
id=i;
}
}
vector<int>f(n+1);
f[id]=a[id];
int up=a[id];
for(int i=id-1;i>=1;i--){
up=min(up,a[i]);
f[i]=up;
}
up=a[id];
for(int i=id+1;i<=n;i++){
up=min(up,a[i]);
f[i]=up;
}
for(int i=1;i<=n;i++)cout<<f[i]<<" ";
}
https://codeforces.com/contest/1407/problem/D[Codeforces Round 669 (Div. 2)](https://codeforces.com/contest/1407)
有 $n$ 个高楼排成一行，每个楼有一个高度 $h_i$。称可以从楼 $i$ 跳到 楼 $j$，当 $i$, $j$ ( $i < j$ )满足以下三个条件之一：
$i+1=j$
$\max(h_{i+1},h_{i+2},\cdots,h_{j-1})<\min(h_i,h_j)$
$\min(h_{i+1},h_{i+2},\cdots,h_{j-1})>\max(h_i,h_j)$
现在你在楼 $1$，请求出跳到楼 $n$ 最少要跳几次。
$2 \leq n \leq 3\cdot 10^5$, $1\leq h_i \leq 10^9$。
在单调栈过程中顺序更新dp。特别需要处理出现相等的情况，保留下标大的。注释里也写了，注意到本题的严格大于小于。本来想图论做的，后来发现需要链好多边，但sugar的做法就是先建图然后直接跑bfs，但这其中贪心的证明没想明白。
int n, m;
int a[N];
int dp[N];
stack<int>mn,mx;
//注意边界的处理，当出现右边没有比当前数的小的时候，这种情况的转移只能转移到下一个相邻
//更多的是转移，而不是下一个比它的大/小的数
//有了转移以后，说是dp，不如说是dag上用dp求最短路
// vector<int>e[N];
// void add(int u,int v){
// e[u].push_back(v);
// }
// 在这道题中，对于相等的点，我们可以直接用后面的覆盖前面的
// ——因为在一系列连续相等点中，转移到其他点都无法移动到更好地方
//只有最后一个能跳到更远处。
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
memset(dp,0x3f,sizeof dp);
dp[1]=0;
auto cal=[&](int u,int v){
dp[v]=min(dp[u]+1,dp[v]);
};
for(int i=1;i<=n;i++){
//严格不等号，不需要特殊处理
while(mn.size()&&a[mn.top()]>a[i]){
cal(mn.top(),i);
mn.pop();
}
if(!mn.empty())cal(mn.top(),i);
//遇到相等的只能保留最后一个，因为保留前面的，有最后一个在，未来的位置也不可能
//也不可能从前面转移，因为要求区间内的数严格小于
if(mn.size()&&a[mn.top()]==a[i])mn.top()=i;
else mn.push(i);
while(mx.size()&&a[mx.top()]<a[i]){
cal(mx.top(),i);
mx.pop();
}
if(!mx.empty())cal(mx.top(),i);
if(mx.size()&&a[mx.top()]==a[i])mx.top()=i;
else mx.push(i);
}
cout<<dp[n]<<endl;
}
int a[N];
int ans[N];int tot=0;
int l[N];int r[N];
void dfs(int u){
ans[u]=++tot;
if(l[u])dfs(l[u]);
if(r[u])dfs(r[u]);
}
void built(){
stack<int>st;
int root=0;
for(int i=1;i<=n;i++){
int last=0;
while(!st.empty()&&a[st.top()]>a[i]){
last=st.top();
st.pop();
}
if(!st.empty())r[st.top()]=i;
else root=i;
l[i]=last;
st.push(i);
}
dfs(root);
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
built();
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}
给一个生成序列，建出一棵笛卡尔树，求字典序最小的可以得到相同笛卡尔树的生成序列(
复杂度 O(N)
#include<bits/stdc++.h>
#define re register
#define il inline
#define LL long long
using namespace std;
template<typename T>il void read(T &ff){
T rr=1;ff=0;re char ch=getchar();
while(!isdigit(ch)){if(ch=='-')rr=-1;ch=getchar();}
while(isdigit(ch)){ff=(ff<<1)+(ff<<3)+(ch^48);ch=getchar();}
ff*=rr;
}
const int N=1e5+7;
int n,a[N],stk[N],ls[N],rs[N];
void dfs(re int x){
if(x)printf("%d ",x),dfs(ls[x]),dfs(rs[x]);
}
signed main(){
read(n);
for(re int i=1,x;i<=n;++i)read(x),a[x]=i;//与笛卡尔树模板不同之处
//这里“把权值当做下标，以下标为权值‘输入’a数组”，就转化成板子啦
for(re int i=1,pos=0,top=0;i<=n;++i){
pos=top;
while(pos&&a[stk[pos]]>a[i])pos--;
if(pos)rs[stk[pos]]=i;
if(pos<top)ls[i]=stk[pos+1];
stk[top=++pos]=i;
}
dfs(stk[1]);
return 0;
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog！