单调队列

单调队列可以求解滑动窗口的最大值和最小值问题，或者处理可加信息。（别忘了第一个）

P1886

有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\) 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e9;
void cmax(int &x, int y) {if(x < y) x = y;}
void cmin(int &x, int y) {if(x > y) x = y;}
int a[1000100];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    int n,k;cin>>n>>k;
    f(i,1,n)cin>>a[i];
    deque<int> q;

    
    f(i, 1, k) {
        while(!q.empty() && a[q.back()] >= a[i]) q.pop_back();
        q.push_back(i);
    }
    cout << a[q.front()] << " ";
    for(int i = 2, j = k + 1; i <= n - k + 1; i ++, j ++) {
        while(!q.empty() && q.front() < i) q.pop_front();
        while(!q.empty() && a[q.back()] >= a[j]) q.pop_back();
        q.push_back(j);
        cout << a[q.front()] << " ";
    }      
    cout << endl;    while(!q.empty()) q.pop_back();
    f(i, 1, k) {
        while(!q.empty() && a[q.back()] <= a[i]) q.pop_back();
        q.push_back(i);
    }
    cout << a[q.front()] << " ";
    for(int i = 2, j = k + 1; i <= n - k + 1; i ++, j ++) {
        while(!q.empty() && q.front() < i) q.pop_front();
        while(!q.empty() && a[q.back()] <= a[j]) q.pop_back();
        q.push_back(j);
        cout << a[q.front()] << " ";
    }  
    cout << endl;
    //time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
}

如何求任意一个固定大小的矩形的最小值？
考虑 \(s_{i,j}\) 表示 \(a_{i,j,...,j+len-1}\) 的最小值，\(t_{i,j}\) 表示 \(s_{i,...,i+len-1,j}\) 的最小值即可。