【每日一题】3月30

单调队列经典模板题。详细可以看代码。

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e6 + 5;
std::deque<int> q[2];// max,min
int n,k;
int a[MAXN];

int A1[MAXN],A2[MAXN];
int main(){
    scanf("%d%d",&n,&k);
    FOR(i,1,n) scanf("%d",a+i);
    FOR(i,1,n){
        while(!q[0].empty() && a[q[0].back()] < a[i]) q[0].pop_back();q[0].pb(i);
        while(!q[0].empty() && q[0].front() < i-k+1) q[0].pop_front();
        if(i >= k) A2[i] = a[q[0].front()];
        while(!q[1].empty() && a[q[1].back()] > a[i]) q[1].pop_back();q[1].pb(i);
        while(!q[1].empty() && q[1].front() < i-k+1) q[1].pop_front();
        if(i >= k) A1[i] = a[q[1].front()];
    }
    FOR(i,k,n) printf("%d ",A1[i]);puts("");
    FOR(i,k,n) printf("%d ",A2[i]);puts("");
    return 0;
}