单调队列

其中元素保持单调性的队列，有删除头部，删除尾部和在尾部插入三种操作。可以用 deque 实现。

模板：P1886

维护一个递减的单调队列，输出队头即为区间最大值，最小值的求法同理。

# include<iostream>
# include<deque>
using namespace std;

const int N=1e6+3;
struct node{
	int id,val;
	void in(int x){
		cin>>val;
		id=x;
	}
}a[N];

int n,k,ai[N],aa[N];
deque<node> mi,ma;

int main(){
	cin>>n>>k;
	for(int i=1;i<=n;++i){
		a[i].in(i);
		while(!mi.empty()&&mi.back().val>a[i].val)
			mi.pop_back();
		if(!mi.empty()&&mi.front().id<=i-k)
			mi.pop_front();
		mi.push_back(a[i]);
		ai[i]=mi.front().val;
		while(!ma.empty()&&ma.back().val<a[i].val)
			ma.pop_back();
		if(!ma.empty()&&ma.front().id<=i-k)
			ma.pop_front();
		ma.push_back(a[i]);
		aa[i]=ma.front().val;
	}
	for(int i=k;i<=n;++i) cout<<ai[i]<<" ";
	cout<<endl;
	for(int i=k;i<=n;++i) cout<<aa[i]<<" ";
	return 0;
}