单调栈和单调队列

P5788

#include <bits/stdc++.h>
using namespace std;
const int N=3e6+5;
int n,a[N],ans[N],top,stk[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		while(top>0 && a[stk[top]]<a[i]){
			ans[stk[top--]]=i;
		}
		stk[++top]=i;
	}
	for(int i=1;i<=n;++i){
		printf("%d ",ans[i]);
	}
	return 0;
}

B3666

#include <bits/stdc++.h>
#define LL unsigned long long
using namespace std;
const int N=1e6+5;
int n,top,stk[N];
LL a[N],ans;
int main(){
	//留在栈中的是后缀最大值
	//利用(a^b)^b=a消除影响
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%llu",&a[i]);
		while(top && a[stk[top]]<=a[i]){
			ans^=stk[top--];
		}
		ans^=i;
		stk[++top]=i;
		printf("%llu\n",ans);
	}
	return 0;
}

P2947

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],stk[N],ans[N],top;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		while(top && a[stk[top]]<a[i]){
			ans[stk[top--]]=i;
		}
		stk[++top]=i;
	}
	for(int i=1;i<=n;++i){
		printf("%d\n",ans[i]);
	}
	return 0;
}

P6510

/*
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,maxx[N][25],ans;
int query(int L,int R){
	int t=log2(R-L+1);
	return max(maxx[L][t],maxx[R-(1<<t)+1][t]);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&maxx[i][0]);
	}
	for(int j=1;j<=20;++j){
		for(int i=1;i+(1<<j)-1<=n;++i){
			maxx[i][j]=max(maxx[i][j-1],maxx[i+(1<<(j-1))][j-1]);
		}
	}
	// printf("%d\n",query(1,2));
	int R=1;
	for(int L=1;L<=n;++L){
		if(L>R) R=L;
		// printf("%d %d\n",L,R);
		while(R<n && maxx[R+1][0]>maxx[L][0]){
			R++;
			if(maxx[R][0]>query(L,R-1) && L!=R){
				ans=max(ans,R-L+1);
			}
		}
		if(L<R && maxx[R][0]>query(L,R-1)){
			ans=max(ans,R-L+1);
		}
	}
	printf("%d",ans);
	return 0;
}
*/
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],stkmax[N],stkmin[N],topmax,topmin,ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		while(topmax && a[stkmax[topmax]]<a[i]) topmax--;
		while(topmin && a[stkmin[topmin]]>=a[i]) topmin--;//等于的值无法作为有端点
		int k=upper_bound(stkmin+1,stkmin+1+topmin,stkmax[topmax])-stkmin;
		if(k!=topmin+1) ans=max(ans,i-stkmin[k]+1);
		stkmax[++topmax]=i;
		stkmin[++topmin]=i;
	}
	//枚举右端点i，左端点一定是1~i的后缀最小值中大于1~i-1的后缀最大值的值
	printf("%d",ans);
	return 0;
}

P6503

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=3e5+5;
int n,top,stk[N],prex[N],sufx[N],pren[N],sufn[N];
LL a[N],ans;
void clear(){
	top=0;
	memset(stk,0,sizeof(stk));
}
int main(){
	scanf("%d",&n);
	//小细节：一边带“=”一边不带“=”是为去重
	for(int i=1;i<=n;++i){
		sufx[i]=sufn[i]=n+1;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		while(top && a[stk[top]]<=a[i]){
			sufx[stk[top--]]=i;
		}
		stk[++top]=i;
	}
	clear();
	for(int i=n;i>=1;--i){
		while(top && a[stk[top]]<a[i]){
			prex[stk[top--]]=i;
		}
		stk[++top]=i;
		// printf("%d\n",stk[top]);
	}
	clear();
	for(int i=1;i<=n;++i){
		while(top && a[stk[top]]>=a[i]){
			sufn[stk[top--]]=i;
		}
		stk[++top]=i;
	}
	clear();
	for(int i=n;i>=1;--i){
		while(top && a[stk[top]]>a[i]){
			pren[stk[top--]]=i;
		}
		stk[++top]=i;
	}
	for(int i=1;i<=n;++i){
		// printf("%d %d\n",prex[i],sufx[i]);
		ans+=a[i]*(sufx[i]-i)*(i-prex[i]);
		ans-=a[i]*(sufn[i]-i)*(i-pren[i]);
		// printf("%lld\n",ans);
	}
	printf("%lld",ans);
	return 0;
}

P1886

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,k,a[N],q[N],L,R,ans1[N],ans2[N];
int main(){
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	L=1;
	for(int i=1;i<=k;++i){
		while(R>=L && a[q[R]]<=a[i]) R--;
		q[++R]=i;
	}
	ans1[k]=a[q[L]];
	for(int i=k+1;i<=n;++i){
		if(i-k==q[L]) L++;
		while(R>=L && a[q[R]]<=a[i]) R--;
		q[++R]=i;
		ans1[i]=a[q[L]];
	}
	memset(q,0,sizeof(q));
	L=1,R=0;
	for(int i=1;i<=k;i++){
		while(R>=L && a[q[R]]>=a[i]) R--;
		q[++R]=i;
	}
	ans2[k]=a[q[L]];
	for(int i=k+1;i<=n;++i){
		if(i-k==q[L]) L++;
		while(R>=L && a[q[R]]>=a[i]) R--;
		q[++R]=i;
		ans2[i]=a[q[L]];
	}
	for(int i=k;i<=n;++i){
		printf("%d ",ans2[i]);
	}
	puts("");
	for(int i=k;i<=n;++i){
		printf("%d ",ans1[i]);
	}
	return 0;
}