【数据结构】[luoguP1886]滑动窗口

题目

接近于单调队列的模板了 根据大小之类的入队出队 代码好理解
代码如下

#include<iostream> #include<cstdio> #include<cctype> using namespace std; #define in = read() typedef long long ll; const ll size = 1000000 + 1000; ll n,k; ll a[size]; ll h,t; ll q[size],p[size]; inline ll read(){ ll num = 0,f = 1; char ch = getchar(); while (!isdigit(ch)){ if(ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)){ num = num*10 + ch - '0'; ch = getchar(); } return num*f; } inline void maxx(){ h = 1; t = 0; for (int i=1;i<=n;i++){ while (h <= t && q[t] <= a[i]) t --; q[++ t] = a[i]; p[t] = i; while (p[h] <= i - k) h ++; if(i >= k) printf("%d ",q[h]); } printf("n"); } inline void minn(){ h =1; t = 0; for (int i=1;i<=n;i++){ while (h <= t && q[t] >= a[i]) t --; q[++ t] = a[i]; p[t] = i; while(p[h] <= i - k) h ++; if(i >= k) printf("%d ",q[h]); } printf("n"); } int main(){ n in; k in; for (int i=1;i<=n;i++) a[i] in; minn(); maxx(); } //COYG