对顶栈学习笔记

对顶栈。

算法流程如下：

• 以一个点为中心，维护前后缀的最大最小值。
• 如果加减前后首位且区间包含中心点，$O(1)$ 维护前后缀。
• 如果不包含中心点，暴力重构，取当前区间的中点作为中心点。

考虑分析复杂度，如果一个长度为 $n$ 的序列被重构了，则至少操作了 $n/2$ 次。所以复杂度是 $O(n)$，其中 $n$ 为操作次数。

对顶栈感觉可以适用于这种双指针强行让你 $O(n)$ 的题目中。如果预处理或者查询有一个可以做到 $O(n\log n)$ 或者以上，就没有使用的必要了，感觉不如 ST 表。

例题

JOI Open 2018 T1 Bubble Sort 2 QOJ 2643

翻译一下，就是让你 $O(n)$ 求一个序列中，满足：
$$
\min\limits_{i=l}^r a_i+\max\limits_{i=l}^r a_i>r-l+1
$$
的最长区间长度。

考虑一个满足要求的区间 $[l,r]$，随便减去不是最大值的端点，则左式不减，右式减小。一定满足。

考虑一种双指针，枚举右端点 $r$，令当前的最大值为 $ans$，则 $l$ 从 $r-ans+1$ 开始向左枚举，判断合法性。

先不考虑判断合法性的复杂度。先考虑正确性。如果枚举到答案区间的最大值，则左端点根据单调性一定会移动答案区间的左端点。

然后来看端点的移动次数，每次为了保证区间的长度大于等于最大值，每次移动右端点时，左端点最多往右移动一格。左端点最多只能向左移动 $O(2n)$ 次，所以移动次数为 $O(n)$ 的。

现在的复杂度瓶颈在于判断区间的合法性。也就是要动态求出区间的最大值和最小值。

学习了对顶栈以后，可以很自然的套用上去。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m,a[maxn];
int L,mid,R,sl[maxn],sr[maxn],ml[maxn],mr[maxn];//min,max
void build(int L,int R) {
	mid=L+R>>1;int i;
	for (sl[mid]=ml[mid]=a[mid],i=mid-1;i>=L;i--) sl[i]=min(sl[i+1],a[i]),ml[i]=max(ml[i+1],a[i]);
	for (sr[mid+1]=mr[mid+1]=a[mid+1],i=mid+2;i<=R;i++) sr[i]=min(sr[i-1],a[i]),mr[i]=max(mr[i-1],a[i]);
}
int query(int l,int r) {
	if (l==r) return 2*a[l];
	return max(mr[r],ml[l])+min(sr[r],sl[l]);
}
void solve(void) {
	int i,ans=0,l=1,r;mid=1;sl[l]=ml[l]=a[l];
	for (i=0;i<=n;i++) sl[i]=sr[i]=ml[i]=mr[i]=0;
	for (r=1;r<=n;r++) {
		if (r>mid+1) sr[r]=min(sr[r-1],a[r]);else sr[r]=a[r];
		if (r>mid+1) mr[r]=max(mr[r-1],a[r]);else mr[r]=a[r];
		if (mid<l||mid>=r) build(l,r);
		if (query(l,r)<=r-l+1) l++;
		else {
			sl[l-1]=min(sl[l],a[l-1]);
			ml[l-1]=max(ml[l],a[l-1]);
			while (l>=2&&query(l-1,r)>r-l+2) {
				l--;
				sl[l-1]=min(sl[l],a[l-1]);
				ml[l-1]=max(ml[l],a[l-1]);
			}
		}
		ans=max(ans,r-l+1);
	}
	printf("%d\n",ans);
}
signed main(void){
	int i,x,y;
	read(n);read(m);
	for (i=1;i<=n;i++) read(a[i]);
	solve();
	while (m--) {
		read(i);
		while (i--) read(x),read(y),swap(a[x],a[y]);
		solve();
	}
	return 0;
}