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

題目連結:http://tioj.infor.org/problems/

---

單調隊列的應用，維護兩條單調隊列，一個存最大值，一個存最小值。然後判一下最大減最小是否恰等於k即可。(單調隊列維護方法就是讓隊列呈現遞(增|減)，在加入元素的時候把比較(小|大)的全部移掉，同時把最(大|小)值移掉，直到他合法。)

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define PB push_back
typedef pair<lld,int> PLI;
typedef pair<int,int> PII;
#define FF first
#define SS second 
const int N = 10000000 + 5;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m;lld k;
	while(cin>>n>>m>>k){
		deque<PLI> mi, mx;
		vector<PII> ans;
		for(int i=1;i<=n;i++){
			lld x; cin>>x;
			while(!mi.empty() and i-mi.front().SS >= m) mi.pop_front();
			while(!mx.empty() and i-mx.front().SS >= m) mx.pop_front();
			while(!mi.empty() and mi.back().FF > x) mi.pop_back();
			while(!mx.empty() and mx.back().FF < x) mx.pop_back();
			mi.push_back({x,i});
			mx.push_back({x,i});
			if(mx.front().FF - mi.front().FF == k)
				ans.PB({max(1, i-m+1), min(i, n)});
		}
		for(int i=n+1;i<=n+m;i++){
			while(!mi.empty() and i-mi.front().SS >= m) mi.pop_front();
			while(!mx.empty() and i-mx.front().SS >= m) mx.pop_front();
			if(mi.empty() or mx.empty()) break;
			if(mx.front().FF - mi.front().FF == k)
				ans.PB({max(1, i-m+1), min(i, n)});
		}
		cout<<ans.size()<<'\n';
		for(auto i:ans) cout<<i.FF<<" "<<i.SS<<'\n';
	}
	return 0;
}