双向单调队列

#include <bits/stdc++.h>
using namespace std;
struct sd{
	int num,val;
}rr;
deque<sd>d1;//单增
deque<sd>d2;//单减
int add[3][1000005];
int main(){
	int n,m,x,cnt=1;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		rr.num=i;rr.val=x;
		while(!d1.empty()&&x>=d1.back().val){
			d1.pop_back();
		}
		while(!d2.empty()&&x<=d2.back().val){
			d2.pop_back();
		}
		d1.push_back(rr);
		d2.push_back(rr);
		while(i-m>=d1.front().num&&!d1.empty()){
			d1.pop_front();
		}
		while(i-m>=d2.front().num&&!d2.empty()){
			d2.pop_front();
		}
		if(i>=m){
			add[0][cnt]=d1.front().val;
			add[1][cnt]=d2.front().val;
			cnt++;
		}
	}
	for(int i=1;i<cnt;i++){
		printf("%d ",add[1][i]);
	}
	printf("\n");
	for(int i=1;i<cnt;i++){
		printf("%d ",add[0][i]);
	}
	return 0;
}