这里希望通过一个小系列(即重学OI)复习学过的一些重要内容

本系列偏向速通式的快速复习或学前预习，不会有大量例题，重在知识点复习，目的在最短的时间内掌握尽可能多的不会的东西

因此更偏向文字解释而不是图解，需要一定想象力

这是 第一集 数据结构基础篇，本篇与提高篇和特别篇交错更新

本集简介:(单调)栈和队列，ST表

part 0: 约定

我们约定一些用词:

时/空线性:时间/空间复杂度为 \(O(n)\)，直接说时空怎么怎么样就是时间空间都是xx复杂度

\(log\) : 本文大多数 \(log\) 都是以 \(2\) 为底，即 \(log_2\)

对数级:就是说复杂度 \(O(logn)\)

\(a_i\) :通常指原数列

part 1: 栈、队列

这种玩意甚至是噗叽组的，简单提一嘴就过

我们可以考虑有这样一个情形:

一个人走到一个很窄只允许一个人过的巷子里，发现是死路

这个时候第二个人也走了进来，第三个人也走了进来

这个时候能出去的人是谁?只有第三个人吧，他出去了前两个才能出去

像这样先进去的反而后出来的数据结构就是 栈

相对的，我们平常也会遇到一种情况:

你制定了一单子计划，第一个写最前面，第二个第三个往后写

执行的时候从第一个开始往第二个第三个执行

这样先入的也就先出去的数据结构称为 队列

代码:
栈

int top,stk[114514];
void push(int x){
	stk[++top]=x;
}
void pop(){
	top--;
}

其中 \(top\) 所代表的就是栈顶。

同理相比各位都能写队列了就不放了(懒)

时空线性

part 2: ST表

这是一个非常强大的东西，但是作者2022年因为不会这个玩意提高组 T2 没写出来 T1没删调试导致保龄(

希望各位学好基础不要再现咱的悲剧

ST表通常维护一些具有可合并性的东西，就是可以分别计算并且不在乎重复计算，比如最大最小值和最大公约数

显然区间和不能重复计算，遂不行

以最大值为例

我们设一个类似 dp 的东西 \(F_{i,j}\) 表示从 \(i\) 这个位置开始(包括 \(i\)) 往后 \(2^j\) 个数的最大值，\(j\) 这一维空间为对数

也就是 \(F_{i,j}\) 管辖 \([i,i+2^j-1]\)

显然的，\(F_{i,0}=a_i\)

我们可以预处理转移 $F_{i,j}=\max(F_{i,j-1},F_{i+2^{j-1},j-1)} $

非常美好，我们这时不妨考虑怎么计算区间 \([l,r]\) 的最大值

一个区间不可能总是 \(2^k\) 的长度，不妨考虑拆成两个区间:一个左端点在 \(l\) 一个右端点在 \(r\)

考虑对左端点的约束:我们希望他的右端点小于等于 \(r\) 且尽可能大

设最终选用 \(F_{l,P}\) 则满足\(l+2^P-1\le r\)，得 \(P\le log(r-l+1)\)，显然log下取整后可以直接作为 \(P\) 的值

考虑右边区间，设最后取用 \(F_{i,P}\) 使得 \(i+2^P-1=r\)，得 \(i=r-2^P+1\) 同时 \(i=r-2^P+1 \ge l\) 可以得出 \(P\le log(r-l+1)\)

这两种情况的 \(P\) 是相等的，都是 \(log(r-l+1)\)

我们只需要合并答案，也就是取 \(\max(F_{l,P},F_{r-2^P+1,P})\)

实现上我们希望不要因为 \(log\) 这样的小函数导致复杂度退化，我们可以预处理 \(log\) 用位运算解决 \(2^P\)

预处理见代码，正确性显然

#include<bits/stdc++.h>
using namespace std;
int F[100005][25];
int n,m;
int Lg[100005]; 
int query_max(int l,int r){
	int P=Lg[r-l+1];
	return max(F[l][P],F[r-(1<<P)+1][P]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	Lg[1]=0;
	for(int i=2;i<=n;i++)Lg[i]=Lg[i>>1]+1;
	for(int i=1;i<=n;i++) cin>>F[i][0];
	for(int j=1;j<=21;j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			F[i][j]=max(F[i][j-1],F[i+(1<<(j-1))][j-1]);
		}
	}
	while(m--){
		int l,r;
		cin>>l>>r;
		cout<<query_max(l,r)<<"\n";
	}
} 

顺带一提，我们也可以维护最小值所在的位置，即预处理时哪边大就更新为哪边，查询同理

这样可以完成一些奇妙操作但是会稍微写起来丑一点，不放代码了就

写完这一部分笔者手都在抖，终于会写ST表了()

part 3 :单调栈/队列

首先是单调栈

单调栈解决的是这样一种问题:求数列中在 \(i\) 之前/后第一个大于/小于 \(a_i\) 的元素(的下标)

以找某元素后面第一个比他大的为例

单调栈本身原理非常简单，我们考虑把每一个元素入栈，第一个直接入栈

对于第 \(i\) 个元素，如果栈顶比他小就入栈，否则不断弹出直到栈顶比他小或者栈空了再把它入栈

每一次加入新元素，都会从栈中弹出一些元素使得栈保持单调，如果新加入的元素可以使得栈中元素弹出的话，那么新加入的元素就是我们要找的第一个大于原先栈顶的元素

所以每一次就在弹栈时更新答案即可。

通常而言我们会在栈里放元素的下标而不是元素的值

代码:

#include<bits/stdc++.h>
using namespace std;
int n,a[3000005],stk[3000005],top,f[3000005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		while(top and a[stk[top]]<a[i]) f[stk[top]]=i,--top;
		stk[++top]=i;
	}
	for(int i=1;i<=n;i++) cout<<f[i]<<" ";
}

其实类似的你也可以认为单调栈维护的是以xx为最值的区间

另一个东西就是单调队列了

和单调栈相反，它维护的是每个长度为 \(k\) 的区间的最值

怎么做到这个效果?首先类似于单调栈，我们维护一个具有单调性的队列，比如队头最小，队尾最大，中间排好序

这样队头/尾就是我们期望找的最值

考虑怎么确保长度小于等于 \(k\)

简单，队头和当前下标的差大于 \(k\) 就扔掉队头，把新的数加在队尾就好

就是那个口诀:一个选手比你小还比你强你就可以退役了

显然我们正着考虑，一个在你后面的元素贡献还比你大你就可以滚(出队)了

否则你会因为年龄过大退役

代码:(最大最小都在里面)

#include<bits/stdc++.h>
using namespace std;
//queue<int> q;
int a[1145141],q[1145141],qq[1145141],aa[1145141];
int main(){
	int n,m;
	cin>>n>>m;
	int r,l,ll,rr; 
	l=r=rr=ll=1;
	for(int i=1;i<=n;i++){cin>>a[i];aa[i]=a[i];}
	r=rr=0;
	q[l]=1;
	qq[ll]=1;
	for(int i=1;i<=n;i++){
		if(i-qq[ll]>=m&&ll<=rr) ll++;//检查区间 
		while(aa[i]<=aa[qq[rr]] && ll<=rr) rr--;
		qq[++rr]=i;
		if(i>=m)cout<<a[qq[ll]]<<" "; 
	}
	cout<<endl;
	for(int i=1;i<=n;i++){
		if(i-q[l]>=m&&l<=r) l++;//检查区间 
		while(a[i]>=a[q[r]] && l<=r) r--;
		q[++r]=i;
		if(i>=m)cout<<a[q[l]]<<" "; 
	}
	return 0;
}

注意的是一开始队尾在队首-1

单调栈通常有一个配套技巧:悬线法

这类问题通常就是对于一个矩阵，有些格子是障碍，选出最大子矩形啊啊之类的

把普通格子视为1，障碍为0，从上往下一行行考虑，维护一个格子往上看最长的长度，单调栈维护往左往右的长度，就是通法

贴一个同学的链接:单调栈单调队列