subject

Problem surface

Given an array with a length of N, a sliding form with a length of K moves from the leftmost end to the rightmost end. You can only see the number of K in the window. Each time the form moves one bit to the right, as shown in the following figure:

window position	minimum value	Maximum
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

Your task is to find out the maximum and minimum values of the form in each position.

Input format

Line 1: two integers N and K; Line 2: N integers, representing N elements of the array (≤ 2e9);

Output format

The first line is the minimum value when the sliding window moves from left to right to each position, and each number is separated by a space; The second line is the maximum value when the sliding window moves from left to right to each position, and each number is separated by a space.

Sample

Input&Output

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

thinking

This problem is the sliding window to find the maximum value problem. The tool we need to use is a two headed monotonic queue.

If the maximum value is found, a decreasing queue should be constructed, and vice versa.

The explanation is as follows:

1. First, when we traverse the array, the current subscript means that the right endpoint of the sliding window is the element. Note that the sliding window size is k.

2. Suppose there is a right endpoint a of the sliding window, and note that the next element of the sliding window is B. for ab, we have two cases: b > = a or B < a (corresponding to points 3 and 4 respectively).

3. B > = A: we know that B is on the right of a, then the range of B's influence is [b,b+k-1], and the range of a's influence is [a,a+k-1]. Because b-a=1, the influence range of B is always larger than that of A. This means that once we can get to point B, a is no longer the maximum. At this time, a has no effect. A goes out of the team first. Before a, there are a-1, a-2 The range they can influence is smaller than a, and it is impossible to become the maximum, so they are also the first team from the team. Until the queue is empty, now B is the new maximum and the first of the queue.

4. b < A: b is smaller, so b can't replace a, but b may become a new maximum where a can't be affected, that is, the point b+k-1. Therefore, we let b join the team from the end of the team, which can be understood as "to be used". It should be noted here that when b enters the team from the end of the team, it should also follow the principle in 3. Therefore, if b is larger than the element at the end of the team, the element at the end of the team is useless. We also leave the element at the end of the team until b is smaller than the element at the end of the team.

5. It should also be noted that the sliding window has a size, so the elements in our queue have a "life cycle", that is, the current subscript - the subscript + 1 of the queue element should be less than or equal to k

So we actually store subscripts in the queue, which is more convenient for reference.

code

#include <iostream>
#include <algorithm>
using namespace std;
//This problem is the problem of sliding window to find the maximum or minimum value
//To apply to a two headed monotone queue, the maximum or minimum value is maintained all the time, and because it is a sliding window, the element has a life cycle. Here, array q is used to simulate
//
int num[1000010];
int q[4000020];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    //
    int n, k;cin >> n >> k;
    for(int i = 0;i < n;++i) cin >> num[i];
    //
    int head, tail;
    //minimum value
    head = 0, tail = 0;
    //Let the first element join the team first
    q[head] = 0;
    for(int i = 0;i < n;++i)
    {
        //If the team head element reaches the life cycle, the team head element leaves the team until the head and tail pointers meet
        while(head <= tail && i-q[head]+1 > k) head++;
        if(num[q[head]] >= num[i])
        {
            //If you are smaller than the first element of the team, you will always be out of the team
            while(head <= tail && num[q[head]] >= num[i]) head++;
            //If you go one more space, you have to go back one space
            q[--head] = i;
        }else
        {
            //Otherwise, join the team from the end of the team, but maintain monotony
            while(head < tail && num[q[tail]] >= num[i]) tail--;
            q[++tail] = i;
        }
        //Output only when and only when you reach the desired sliding window size
        if(i >= k-1) printf("%d ", num[q[head]]);
    }
    printf("\n");
    //Maximum
    head = 0, tail = 0;
    q[head] = 0;
    for(int i = 0;i < n;++i)
    {
        while(head <= tail && i-q[head]+1 > k) head++;
        if(num[q[head]] <= num[i])
        {
            while(head <= tail && num[q[head]] <= num[i]) head++;
            q[--head] = i;
        }else
        {
            while(head < tail && num[q[tail]] <= num[i]) tail--;
            q[++tail] = i;
        }
        if(i >= k-1) printf("%d ", num[q[head]]);
    }
    printf("\n");
    return 0;
}
//