[TIOJ]1566. 簡單易懂的現代都市

題目連結：http://tioj.infor.org/problems/1566
可以使用單調對列優化，用deque維護區間最大值和區間最小值。

#include <iostream>
#include <deque>
#include <vector>
#define F first
#define S second
#define ll long long
using namespace std;
typedef pair<ll,int> Pair;
int main(){
    int n,m;
    ll k;
    cin >> n >> m >> k;
    deque <Pair> mx,mn;
    vector<Pair> ans;
    int l = 1;
    for(int i = 1 ; i <= n ; i++){
        ll a;cin >> a;
        if(i > m)l++;
        if(mx.size() && mx.front().S + m <= i)mx.pop_front();
        if(mn.size() && mn.front().S + m <= i)mn.pop_front();
        while(mx.size() && mx.back().F < a)mx.pop_back();
        while(mn.size() && mn.back().F > a)mn.pop_back();
        mx.push_back({a,i}),mn.push_back({a,i});
        if(mx.front().F - mn.front().F == k && i-l >= 1)ans.push_back({l,i});
    }
    l++;
    while((n-l) >= 1){
        while(mx.size() && mx.front().S < l)mx.pop_front();
        while(mn.size() && mn.front().S < l)mn.pop_front();
        if(mx.front().F - mn.front().F == k)ans.push_back({l,n});
        l++;
    }
    cout << ans.size() << endl;
    for(Pair i : ans)cout << i.F << ' ' << i.S << endl;
    return 0;
}