Learning monotone queue

P1886 sliding window

This problem is a basic exercise in a monotonous queue. Because of time, I won't say more here. I saw a good problem solution here * reprinted * and explained it in great detail. I believe you can understand it if you look at it carefully.

Monotone queues have two properties

The order of the elements in the queue in the original list must be monotonically increasing.

The size of the elements in the queue must be monotonic * (increase / decrease / even custom)

The difference between a monotone queue and a normal queue is that monotone queues can be either out of the queue at the beginning or out of the queue at the end.

So how do we implement monotone queues?

Let's take the example and set the minimum as the standard.

8 3
1 3 -1 -3 5 3 6 7

*In the following, we use q to represent the monotone queue, and p to represent its corresponding sequence number in the original list.

1. Since there is no element in the team at this time, we directly make 1 into the team. At this point, q={1},p={1}.

2. Now 3 faces a choice. The following is based on the idea that if you put 3 in, if the next two numbers are larger than it, then 3 may become the smallest in its lifetime. At this point, q={1,3},p={1,2}

3. A -1 appears below. The tail element 3 is larger than -1, which means that as long as -1 enters the team, 3 will not be the minimum value in its lifetime. The reason is obvious: when the following 3 is framed, then -1 must also be framed, so 3 can never be the minimum value. So, 3 left the team at the end of the team. Similarly, 1 leaves the team from the end of the team. Finally -1 enters the team. At this time, q={-1},p={3}

4. When -3 appears, as analyzed above, -1>-3, -1 leaves the team from the end of the team and -3 enters the team from the end of the team. q={-3}, p={4}.

5. There are 5, because 5>-3, as analyzed in the second article, 5 is still promising in his lifetime, so 5 is in the team. At this point, q={-3,5},p={4,5}

6. 3 appears. 3. Compare with 5 at the end of the team, 3<5. According to the analysis in Article 3, 5 leaves the team from the end of the team. 3. Compare it with -3, the same as the second analysis, and 3 enters the team. At this point, q={-3,3},p={4,6}

7. 6 appears. 6 compared with 3, because 3<6, 3 does not need to be out of the team. Since the elements before 3 are less than 3, there is no need to compare them, and 6 are in the team. Since -3 is already outside the sliding window at this time, -3 leaves the team first. At this point, q={3,6},p={6,7}

8. 7 appears. Element 6 at the end of the team is less than 7, and 7 enters the team. At this point, q={3,6,7},p={6,7,8}.

Then, we have analyzed the basic operations of monotone queues. Because the size of elements in a monotonic queue is monotonically increasing * (increase / decrease / user-defined comparison), the first element of the queue must be the maximum value. Output according to the meaning of the question.

Here's the code. In order to make it easier for everyone to copy (cross out), I'll write some comments. Anyway, it's already clear in the front.

    #include<cstdio>
    #include<cstring>
    using namespace std; 
    struct Monotone_queue
    {
        static const int maxn=1000001;
        int n,k,a[maxn];
        int q[maxn],head,tail,p[maxn];//Like the topic description, q is a monotonic queue and p is the corresponding number.
        void read()
        {
            scanf("%d %d",&n,&k);
            for(int i=1;i<=n;++i)
                scanf("%d",&a[i]);}//No need to say
        void monotone_max()//Monotonic maximum
        {
            head=1;
            tail=0;
            for(int i=1;i<=n;++i)
            {
                while(head<=tail&&q[tail]<=a[i])
                    tail--;
                q[++tail]=a[i];
                p[tail]=i;
                while(p[head]<=i-k)
                    head++;//☣
                if(i>=k)printf("%d ",q[head]);
            }
            printf("\n");
        }
        void monotone_min()
        {
            head=1;
            tail=0;//Why? Because the head must strictly correspond to the first element and the tail must strictly correspond to the tail element, when tail>=head, it indicates that there are elements. At the beginning, the queue is empty, so it is necessary to assign values in this way. In fact, this is the same as an ordinary queue.
            for(int i=1;i<=n;++i)
            {//a[i] indicates the current value to be processed
                while(head<=tail&&q[tail]>=a[i])
                    tail--;//As long as there are elements in the queue and the tail element is larger than the value to be processed, it means that the tail element can no longer appear in the queue, so it is out of the queue. Until the tail element is smaller than the value to be processed, the monotonicity is satisfied.
                q[++tail]=a[i];//The value to be processed is queued.
                p[tail]=i;//Save its number at the same time
                while(p[head]<=i-k)
                    head++;//If the first element of the team is "obsolete", leave the team.
                if(i>=k)printf("%d ",q[head]);//Output the maximum value, that is, the first element of the queue. i> =k indicates the output. As for why, you can see the topic by yourself.
            }
            printf("\n");
        }
    }worker;
    int main()
    {
        worker.read();
        worker.monotone_min();
        worker.monotone_max();
        return 0;
    }
Downstairs is the code I wrote. It's a little ugly. I'll see!
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    int q[1000005],num[1000005],ch[1000005];
    int main()
    {
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&ch[i]);
        }
        int head=0,tail=1;
        for(int i=1;i<=n;++i)
        {
            while(ch[i]<=q[tail]&&head<=tail)//
            //Note: head<=tail has an equal sign because we can make the queue pop up from the back until it is empty. At this time, head=tail-1 (eg:head=1, tail=0) is satisfied (because we have not yet performed the insertion operation) 
             tail--;
            tail++;
            q[tail]=ch[i];
            num[tail]=i;
            while(i-num[head]>=k)//Pay attention to the equal sign, because it is necessary to ensure that a space is left for the next insertion! 
             head++;
            if(i>=k) printf("%d ",q[head]);
        }
        memset(num,0,sizeof(num));
        memset(q,0,sizeof(q));
        printf("\n");
        head=0;tail=1;
        for(int i=1;i<=n;++i)
        {
            while(ch[i]>=q[tail]&&head<=tail)//
            //Note: head<=tail has an equal sign because we can make the queue pop up from the back until it is empty. At this time, head=tail-1 (eg:head=1, tail=0) is satisfied (because we have not yet performed the insertion operation) 
             tail--;
            tail++;
            q[tail]=ch[i];
            num[tail]=i;
            while(i-num[head]>=k)//Pay attention to the equal sign, because it is necessary to ensure that a space is left for the next insertion! 
             head++;
            if(i>=k) printf("%d ",q[head]);
        }
        return 0;
    }
P.s:
Pay attention to the comments identified in the code, which are very error prone!!!

Tags: OI

Posted by invincible_virus on Mon, 30 May 2022 00:24:33 +0530