P1886-单调队列【黄】

一道普普通通的模版题，让我想起了此前做过的绿题P1725，于是运用相同的知识轻松切掉本题

Code

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#define int long long
using namespace std;
int N,k,tmax[1000000+5],tmin[1000000+5];
struct p{int da,no;} a[1000000+5];
deque<p> qmax,qmin;
signed main()
{
	cin>>N>>k;
	for(int i=1;i<=N;i++)
	{
		cin>>a[i].da;
		a[i].no=i;
	}

	for(int i=1;i<=k;i++)
	{
		while(!qmax.empty()&&qmax.back().da<=a[i].da)qmax.pop_back();
		qmax.push_back(a[i]);
		while(!qmin.empty()&&qmin.back().da>=a[i].da)qmin.pop_back();
		qmin.push_back(a[i]);
		tmax[1]=qmax.front().da;
		tmin[1]=qmin.front().da;
	}
	for(int i=2;i<=N-k+1;i++)
	{
		while(!qmax.empty()&&qmax.back().da<=a[i+k-1].da)qmax.pop_back();
		qmax.push_back(a[i+k-1]);
		while(!qmin.empty()&&qmin.back().da>=a[i+k-1].da)qmin.pop_back();
		qmin.push_back(a[i+k-1]);
		while(!qmax.empty()&&qmax.front().no<i)qmax.pop_front();
		while(!qmin.empty()&&qmin.front().no<i)qmin.pop_front();
		tmax[i]=qmax.front().da;
		tmin[i]=qmin.front().da;
	}
	for(int i=1;i<=N-k+1;i++)cout<<tmin[i]<<' ';
	cout<<endl;
	for(int i=1;i<=N-k+1;i++)cout<<tmax[i]<<' ';
	return 0;
}