Some nonsense:

In memory of hin, a long time ago, the elder gellygoat told us about the monotonous queue that never moved again in his nest.

qbxt's computer compiled once 9s+ can starfish.

f10 is really good.

Topic transfer

Does the data look like it can be clipped by a line segment tree?

As a board question of monotone queue, this question is of course monotone queue.

Here, we set up two monotonous queues (dalao uses one, but I am not dalao, only two)

Since it is a monotonous queue, the elements in the queue must be monotonous. But note that monotonous queues are not priority queues

A monotonic queue is actually a double-ended queue

First, paste the functions commonly used in double-ended queues.

Insert:

Insert from the team head: q.push_front();

Insert from the end of the team: q.push_back();

Insert an element x: iterator insert (iterator it, const T&x) before an element of a double-ended queue

Add n identical elements x: void insert (iterator it, int n, const T&x) before one element in the double-ended queue

Delete:

Delete the element of the team head: q.pop_front()

Delete the element at the end of the queue: q.pop_back()

Clear queue: q.clear()

Delete an element: Iterator erase(iterator it)

See More Usage Here

Take the team that maintains the minimum as an example.

Our maintenance team head is the minimum of the current interval.

If the subscript of the first number of the current queue is less than now (the left end of the current slider), it is time to retire and pop out (note that the queue is not empty)

We insert a new number from the end of the team. If the current number of the end of the team is larger than a[x] (the number to be inserted), then the subscript of the number of the end of the team must be smaller than x, and it will lose effect earlier than a[x]. From this point of view, the current number of team tails can not be the smallest candidate, so we pop it out.

After the above two rounds of pop, you can put a[x] at the end of the team.

Let's see the details.

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
using namespace std;
inline int read()
{
    char ch=getchar();
    int x=0;bool f=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f?-x:x;
}
int now,n,k,a[1000009],mi[1000009],ma[1000009],cnt;
struct dl{
    int xb,zhi;//Queues are structured types that record subscript and number values
    dl(int xx,int yy):xb(xx),zhi(yy){}//Constructor
};
deque<dl> qma,qmi;//qma Maintain maximum value. qmi Maintenance minimum
void pshmax(int x)
{
    while(!qma.empty()&&qma.front().xb<now) qma.pop_front();//Note that the queue is not empty( RE Warning)
    while(!qma.empty()&&qma.back().zhi<a[x])qma.pop_back();
    qma.push_back(dl(x,a[x]));

}
void pshmin(int x)
{
    while(!qmi.empty()&&qmi.front().xb<now) qmi.pop_front();
    while(!qmi.empty()&&qmi.back().zhi>a[x])qmi.pop_back();
    qmi.push_back(dl(x,a[x]));
   
}
void luangao()
{
    for(now=2;now+k-1<=n;now++)//Plus is k-1 ah k-1
    {
        pshmin(now+k-1);pshmax(now+k-1);
        mi[++cnt]=qmi.front().zhi;
        ma[cnt]=qma.front().zhi;
    }
}
int main()
{
    n=read();k=read();
    for(int i=1;i<=n;i++)
     a[i]=read();
    qma.push_back(dl(1,a[1]));
    qmi.push_back(dl(1,a[1]));
    for(int i=2;i<=k;i++)//Manual processing first[1,k]This interval
     {
         pshmax(i);
        pshmin(i);
     }
     ma[1]=qma.front().zhi;
     mi[1]=qmi.front().zhi;
     cnt=1;
    luangao();
    for(int i=1;i<=cnt;i++)
     printf("%d ",mi[i]);
    printf("\n");
    for(int i=1;i<=cnt;i++)
     printf("%d ",ma[i]); 
}