模板

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e6+6;
#define pii pair<int,int>
#define fi first
#define se second
int n,a[N],top,b[N];
pii st[N];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=n;i;i--){	
		while(top&&a[i]>=st[top].fi){
			top--;
		}
		if(!top)b[i]=0;
		else{
			b[i]=st[top].se;
		}
		st[++top].fi=a[i],st[top].se=i;
	}
	for(int i=1;i<=n;i++)cout<<b[i]<<" ";
	return 0;
}

解析

求每个数后第一个大于他的数

从后往前，用栈去做一个东西：每次加一个数进来，比较他跟栈顶，如果他比栈顶小则直接放入，否则弹出栈顶直到栈顶比这个数大，放入这个数

一句话概括就是维护一个单调递减的栈

为什么这么做？

要找第一个比他大的，那么如果一个小数在一个大数后面，那么他一定不会对前面的数的答案有贡献（全被前面那个大数挡上了）

但是如果前面的数比后面的小，那么后面的数还是有用的（碰到一个介于两者之间的数）

这就是所谓的 如果一个人比你小还比你巨，那么你就没用了

其实碰见云落哥哥的我早就没用了

优化

无

应用

云落姐姐说咕了

例题

求数列所有后缀最大值的位置

唔

读不懂题

幸好有天天 AK 的云落大巨

后缀最大值

我们会发现

如果一个数在你后面还比你大

那么你无论如何都成为不了后缀最大值

那么维护一个单调递减的单调栈即可

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

奶牛排队

突然想到，上面两道题根本不用 pair，直接记下标，取值的时候套个 a 即可

呜呜呜，我好菜

云落哥哥救我~

嘻嘻

圆规正转

我们枚举 \(B\)

那么 \(A\) 一定是 \(1-B\) 的后缀最小值的位置

并且由于 \(B\) 要是区间最大值，也就是说，第二个后缀最大值的位置一定在 \(A\) 左面

那么我们就通过 第二个后缀最大值的位置，二分出最靠右的 \(A\) 的位置

上面的后缀最大值和后缀最小值就用单调栈求

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,ans,topx,topn;
int a[N],stx[N],stn[N];
int main() {
  cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i];
  for(int i=1;i<=n;i++) {
    while(topn&&a[stn[topn]]>=a[i])topn--;
    while(topx&&a[stx[topx]]<a[i])topx--;
    int k=upper_bound(stn+1,stn+1+topn,stx[topx])-stn;
    if(k!=(topn+1)){
      ans=max(ans,i-stn[k]+1);
    }
    stn[++topn]=i;
    stx[++topx]=i;
  }
  cout<<ans;
  return 0;
}

DIFERENCIJA

这是一个经典操作：找到一个值为为最大值的最大区间长度/区间个数

那么在单调栈里这个数的前一个数就是他的左边界限，反过来做一下就能确定右端点

最小值一样

直接贴一个很清晰的题解代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<stack>

#define int long long
const int MN=3e5+5;

using namespace std;

int a[MN];
int Lmax[MN],Rmax[MN],Lmin[MN],Rmin[MN];
stack<int>s;
int n;

signed main(void){

    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];

    for(int i=1;i<=n;i++){
        while(!s.empty()&&a[s.top()]<=a[i])s.pop();
        if(s.empty())Lmax[i]=0;
        else Lmax[i]=s.top();
        s.push(i);
    }

    while(!s.empty())s.pop();
    for(int i=1;i<=n;i++){
        while(!s.empty()&&a[s.top()]>=a[i])s.pop();
        if(s.empty())Lmin[i]=0;
        else Lmin[i]=s.top();
        s.push(i);
    }

    while(!s.empty())s.pop();
    for(int i=n;i>=1;i--){
        while(!s.empty()&&a[s.top()]<a[i])s.pop();
        if(s.empty())Rmax[i]=n+1;
        else Rmax[i]=s.top();
        s.push(i);
    }

    while(!s.empty())s.pop();
    for(int i=n;i>=1;i--){
        while(!s.empty()&&a[s.top()]>a[i])s.pop();
        if(s.empty())Rmin[i]=n+1;
        else Rmin[i]=s.top();
        s.push(i);
    }

    int ans=0;
    for(int i=1;i<=n;i++){
        ans=ans+a[i]*(i-Lmax[i])*(Rmax[i]-i);
        ans=ans-a[i]*(i-Lmin[i])*(Rmin[i]-i);
    }

    cout<<ans<<endl;

    return 0;
}

パッと光って咲いた

花火を見ていた