天降甘霖

问题描述

不知道又走了几天，眼前是一片整齐的青石地砖。不管是谁看上一眼，就知道这绝对不是自然生成的。当小 L 踏上青石地板的一瞬间，原本晴朗的天空迅速暗了下来。紧接着乌云密布，下起了雨。雨很快就停了，紧接着天空瞬间放晴，开始升温。潮湿的青石板被很快晒干。

“这是夏天了吗，雨来得快去得也快啊。”长时间孤身一人，小 L 经常自言自语。

但敏锐的 小 L 发现，有一些青石板上的痕迹没有被完全晒干，雨痕竟然拼成了数字。

有 一行 $n$ 个数。输出每 $k$ 个相邻数字的最大值和最小值。

输入格式

第一行两个整数 $n,k$, $1\le k\le n\le10^6$
第二行，有 $n$ 个数字，中间用空格隔开，每一个数为大小不超过 $10^9$ 的正整数。

输出格式

有两行，每行 $n-k+1$ 个数字，第一行表示最小值，第二行表示最大值。

样例输入

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

样例输出

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

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, k, t;
deque<pair<ll,ll>> iq, dq;
//263ms
vector<ll> ans2;
//288ms
//list<ll> ans2;

void ipush_back(const ll& ele, const ll& cnt/*现在插的元素是第几个，从1开始编号*/) {  // 单调递增队列，队首是区间最小值
    while (!iq.empty() and iq.front().second <cnt-k+1)
        iq.pop_front();
    while (!iq.empty() and iq.back().first > ele)
        iq.pop_back();
    iq.emplace_back(ele,cnt);
}

void dpush_back(const ll& ele, const ll& cnt) {  // 单调递减队列，队首是区间最大值
    while (!dq.empty() and dq.front().second <cnt-k+1)
        dq.pop_front();
    while (!dq.empty() and dq.back().first < ele)
        dq.pop_back();
    dq.emplace_back(ele,cnt);
}

int main(){
    cin >> n >> k;
    for (ll i = 1; i <= n;++i){
        scanf("%lld", &t);
        ipush_back(t, i);
        dpush_back(t, i);
        if(i>=k){
            printf("%lld ", iq.front().first);
            ans2.emplace_back(dq.front().first);
        }
    }
    printf("\n");
    for(auto&i:ans2)
        printf("%lld ", i);
    return 0;
}