Monotonic queue, Luogu p1886 sliding window

A monotonous queue

We all know that queues are a first in, first out structure , Monotonic queue, as its name implies, is an increasing or decreasing queue . Because the elements used are in the team and out of the team once , So its time complexity is O(n).

The scope of monotonic queue

So when do we usually use monotonic queues ？
Generally, monotonic queues are considered in finding the maximum or minimum value in a certain range ,（ Of course, the segment tree can also be in nlog(n) Within the time required )

Example

Next, we will explain how to use monotone queues with an example Luogu P1886 The sliding window ( Click to enter the official website of Luogu to submit ).
The main idea of the topic ：
There's a long one for n Sequence a, And a size of k The window of . Now this one slides from the left to the right , Slide one unit at a time , Find the maximum and minimum values in the window after each slide .
Input n,k, And sequence a, among n Is a sequence a Size ,k For the window size .（1<=k<=n<=10⁶）
Output the maximum and minimum values of each window slide .

Read the meaning of the topic we Soon You can come up with an idea of violent cracking , Enumerate one with a size of k The range of , Then compare the maximum value , But the time complexity will be as high as O(nm), A proper timeout .

Ideas ：
At this point, we wonder if we can maintain a queue que（ Because we traverse from front to back a, Meet the conditions of first in, first out , Consider using queues ）,que The content of maintenance is structure , The content of the structure is the size and subscript of the element ,que.front() Is the maximum value of the corresponding window , We traverse this sequence a, If at present que The header element of is not in the corresponding range of this window （ I.e. subscript over bound ）, Then you can go from que The element pops up in the header (que.pop_front()), Suppose the currently traversed element a[i], If a[i]>=que.back(), It means that a[i] Than que.back() More qualified to become the maximum value of the current window , So you can discard the tail element （que.pop_back()）, until a[i]<que.back(), Then add this element que Tail of （que.push_back(a[i])）, use while Loops can easily accomplish this step . Here we are O(n) The maximum value of all windows is calculated in the time of , The minimum value can also be calculated in the same way , Take a close look at que Internally maintained values , We find that the value of its element satisfies the law of monotonic decreasing , So it's a monotonous queue ..

Not much said , Go straight up AC Code .

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
const int maxn=2e6+286;
int st[2][2002000]; // For storing answers 

typedef struct node   // Define the structure used to store the subscript and size of the element 
{
    
  int id,val;         // Subscript 、 size 
};  

node a[maxn];        // For storing sequences a

deque<node> que1,que2;  //que1 Maintenance maximum , That is, monotonically decreasing queues （ The header element is the maximum ）
                        //que2 Maintenance minimum , That is, monotonically increasing queues （ The header element is the minimum ）
int main()
{
    
   
    int n,k;
    int cnt=0;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)     // Read in sequence a
    {
    
        scanf("%d",&a[i].val);
        a[i].id=i;
    }                 
    
    for(int i=1;i<=n;i++)     // Ergodic sequence a
    {
    
        /*  If a[i]>=que.back(), It means that a[i] Than que.back() More qualified to become the maximum value of the current window ,  So you can discard the tail element （que.pop_back()） */
         while(!que1.empty()&&a[i].val>=que1.back().val)  
              que1.pop_back();
              
        /*  If a[i]<=que.back(), It means that a[i] Than que.back() More qualified to become the minimum value of the current window ,  So you can discard the tail element （que.pop_back()） */
         while(!que2.empty()&&a[i].val<=que2.back().val)
              que2.pop_back();
        
         que1.push_back(a[i]);  // Add the current element to que
         que2.push_back(a[i]);
        
         while(i-k>=que1.front().id)
              que1.pop_front();    // The currently maintained header element is not within the scope of the window , That is, the subscript is out of bounds , Delete the head element 
         while(i-k>=que2.front().id)
              que2.pop_front();
        if(i>=k)   // Store answers 
        {
    
            st[1][++cnt]=que1.front().val;
            st[0][cnt]=que2.front().val;
        }
    }
    // Output the answer 
    for(int i=1;i<=cnt;i++)
        printf("%d ",st[0][i]);
    printf("\n");
    for(int i=1;i<=cnt;i++)
        printf("%d ",st[1][i]);

    return 0;
}

I hope you can have a further understanding of monotonic queues here , Gain something .
I wish you all the best ！！！