从单调栈到笛卡尔树

功能1：单调栈可以在线性时间内为每个数找到序列中下一个比它的大的数，以及上一个比它大的数

https://vjudge.net/problem/POJ-2796单调栈基本功能代表作

poj的c++98首先对size函数不是O（1）的，然后还卡关了同步流的cin，关键数据范围才1e5,逆天毒瘤，耽误我40min，以后poj的题目先测试一下是不是卡常数。然后我不熟悉printf的输出longlong，应该用%lld

题意：给定一个数组，找到一个区间，使得 最大化 区间里的数的和×\times区间最小值

Sol：直接单调栈维护每个数作为最小值能到的左右边界，然后O（n)枚举更新答案即可，前缀和优化一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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

nn 个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人 aa 和 bb，如果他们是相邻或他们之间没有人比 aa 或 bb 高，那么他们是可以互相看得见的。写一个程序计算出有多少对人可以互相看见。

Sol：考虑偏序关系，我们只向左看保证不重复。题目的意思是两个人之间没有高的障碍物，因为要相互看见，每次找到左边第一个比当前数大的数，中间的数删除。如果从头开始做这个过程，会发现保存的序列是单调递减的，只保留了关键点。答案的累加过程中。接下来是本题的一个处理难点，就是连续的相同的元素，我们考虑用pair在插入的时候记录出现了几次，保证元素的值在栈中唯一。

debug：1.每次要判是否存在左边第一个比当前数大的数，这个数也会对答案贡献。

2。要开longlong。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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≤n≤5000001 \leq n \leq 500000。给定一个数组，每个位置填数，最大可以填到a[i]，给了一些限制，要求你最大化的填的数字总和。如果规范地表示，让我们把地编上一个编号从 11 到 nn。那么如果在第 ii 块地的摩天大厦有 aia_i 层，那么我们需要保证 1≤ansi≤ai1 \le ans_i \le a_i。另外，这里不可以有整数 jj 和 kk 满足 j<i<kj < i < k 并且 ansj>ansi<anskans_j > ans_i < ans_k。第 j,kj, k 块地并不需要与第 ii 块地相邻。

Sol；好的dp往往需要先贪心才能出思路或有想法，需要先冷静分析。对于题目的限制条件我们为了避免出现极小值，最多只能有一次下降，所以一般情况是填的数字先单增再单减。

根据这个我们得到一个O(n2)O(n^2)的做法，我们枚举最高点的位置，然后花费O(n)O(n)的代价去向左右递推本次数的和，这个递推是简单的。这个做法可以过掉c1版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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)O(1)计算了。我们考虑预处理

image-20240510211059061

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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/DCodeforces Round 669 (Div. 2)

有 nn 个高楼排成一行，每个楼有一个高度 hih_i。称可以从楼 ii 跳到 楼 jj，当 ii, jj ( i<ji < j )满足以下三个条件之一：

  • i+1=ji+1=j

  • max⁡(hi+1,hi+2,⋯ ,hj−1)<min⁡(hi,hj)\max(h_{i+1},h_{i+2},\cdots,h_{j-1})<\min(h_i,h_j)

  • min⁡(hi+1,hi+2,⋯ ,hj−1)>max⁡(hi,hj)\min(h_{i+1},h_{i+2},\cdots,h_{j-1})>\max(h_i,h_j)

现在你在楼 11，请求出跳到楼 nn 最少要跳几次。

2≤n≤3⋅1052 \leq n \leq 3\cdot 10^5, 1≤hi≤1091\leq h_i \leq 10^9。

在单调栈过程中顺序更新dp。特别需要处理出现相等的情况，保留下标大的。注释里也写了，注意到本题的严格大于小于。本来想图论做的，后来发现需要链好多边，但sugar的做法就是先建图然后直接跑bfs，但这其中贪心的证明没想明白。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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;
       
}

image-20240512041019622

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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]<<" ";
}

给一个生成序列，建出一棵笛卡尔树，求字典序最小的可以得到相同笛卡尔树的生成序列(

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
复杂度 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;
}