单调队列

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,k,a[1000005];
    cin >> n >> k;
    for(int i=1;i<=n;i++)cin >> a[i];
    {
    	deque<int>q;
        for(int i=1;i<=n;i++){
        	while(!q.empty() and q.front()+k<=i)q.pop_front();
            while(!q.empty() and a[q.back()]>=a[i])q.pop_back();
            q.push_back(i);
            if(i>=k)cout << a[q.front()] << " ";
        }
    }
    cout << endl;
    {
    	deque<int>q;
        for(int i=1;i<=n;i++){
        	while(!q.empty() and q.front()+k<=i)q.pop_front();
            while(!q.empty() and a[q.back()]<=a[i])q.pop_back();
            q.push_back(i);
            if(i>=k)cout << a[q.front()] << " ";
        }
    }
}