栈和队列是很郝咏的Stl，那么，我们手搓——用数组模拟
故事背景：辣鸡老o在学单调栈&单调队列
——我栈
top为栈顶，易得出出栈即top--，入栈++top=(ovo)......
——完全不会讲，那么上马：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=114514;
int stk[N],top=0;
/*
inline int read(){
int wow=0,f=1;
char c=getchar();
while(c>'9' || c<'0'){
if(c=='-') f=-f;
c=getchar();
}
while(c>='0' && c<='9'){
wow=(wow<<3)+(wow<<1)+c-'0';
c=getchar();
}
return f*wow;
}
*/
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int q;//q次操作
cin>>q;
for(int i=1;i<=q;i++){
int x,c;
cin>>x;
if(x==1){//入栈
cin>>c;
stk[++top]=c;
}
else{//出栈
if(top<1){
cout<<"EMPTY!\n";
}
else{
cout<<stk[top--]<<"\n";
}
}
}
return 0;
}
——我队列
head为队头，tail为队尾，出队head++，入队++tail=（ovo）......
——上马
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=114514;
int que[N],head=1,tail=0;
//消失的快读
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int q;
cin>>q;
for(int i=1;i<=q;i++){
int x,c;
cin>>x;
if(x==1){
cin>>c;
que[++tail]=c;
}
else{
if(head==tail+1){
cout<<"EMPTY!\n";
}
else{
cout<<que[head++]<<"\n";
}
}
}
return 0;
}
——我记得我是要学单调栈来着
单调栈，记录依托数组中某个元素之前（后）的第一个大于或小于它的元素，并可以在O（n）的时间内完成（也许解释的很狭义）——
当我在黑暗中积蓄的情绪，期待光明降临时，突然降临的一束光，让我所有的情绪全部爆发了
当我的栈中的所有元素单调减，没有弹出的希望，突然出现一个大于当前序列中部分元素（即可）的数，栈中的小于该元素的元素的ans全部重置为该元素的下标
——压入一个元素（的下标，能快速在原数组中找到对应值的那种啦）时只有两种情况：
1.一刀切若干元素，并当栈顶
2.仅入栈
——很啰嗦，所以上马
点击查看代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int wow=0,f=1;
char c=getchar();
while(c>'9' || c<'0'){
if(c=='-'){
f=-f;
}
c=getchar();
}
while(c>='0' && c<='9'){
wow=(wow<<3)+(wow<<1)+c-'0';
c=getchar();
}
return wow*f;
}
const int N=3e6+5;
int n,a[N],ans[N],q[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++) a[i]=read();
int top=0;
for(int i=1;i<=n;i++){
while(top>0 && a[q[top]]<a[i]){
ans[q[top]]=i;
top--;
}
q[++top]=i;
}
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
}
——那么，单调队列
单调队列是用来解决一个定长区间中的最大值问题的一种可爱的竖锯结垢（此处致敬xxxxx26），其实现思路是向一个手搓plus版——可以从头出队，从头入队，从尾出队的队列中压入元素（话说为什么叫压入）（的下标）
压入元素时，若该元素比原队列中元素更优，那将该元素出队
——如果一个oier比你小，还比你强，你就没有存在的意义了
（stop！！！）
第二种出队方法在下标超过区间范围是自然出队
——上高三了
——仍然很啰嗦，也很容易破防，所以上马
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,k;
const int N=1e6+12;
int a[N];
int que[N];
int head=1,tail=0;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
int j=i;
while(head<=tail && a[que[tail]]>=a[i]){
tail--;
}
que[++tail]=i;
if(que[head]<i-k+1) head++;
if(i>=k) cout<<a[que[head]]<<" ";
}cout<<"\n";
head=1,tail=0;
for(int i=1;i<=n;i++){
int j=i;
while(head<=tail && a[que[tail]]<=a[i]){
tail--;
}
que[++tail]=i;
if(que[head]<i-k+1) head++;
if(i>=k) cout<<a[que[head]]<<" ";
}
return 0;
}