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

題目鏈接:https://tioj.ck.tp.edu.tw/problems/1566

維護兩個m大小的單調佇列
一個遞增一個遞減
分別代表區間最大值和區間最小值
遞增的單調佇列中
當\(v_j\ >\ v_i\)且\(i\ <\ j\)時
\(v_i\)會比\(v_j\)早被pop掉且\(v_j\)在時\(v_i\)沒有存在的意義
遞減的同理
再處理超出區間的值pop掉這個問題就解決啦
不過有個小細節我一直不知道
就是\(2^{31}\)是2147483648
超出int範圍的2147483647
所以要開long long

以下為code

#include<bits/stdc++.h>

#include<bits/extc++.h>

using namespace std;

using namespace __gnu_cxx;

using namespace __gnu_pbds;

using ll = long long;

#define AC ios::sync_with_stdio(0),cin.tie(0);

int main()

{

AC

int n,m,l=1;

ll k,t;

cin>>n>>m>>k;

deque<pair<ll,int>> mx,mn;

queue<pair<ll,int>> q;

for(int i=1;i<=n;i++)

{

cin>>t;

if(i>m) l++;

while(mx.size()&&i-mx.front().second>=m) mx.pop_front();

while(mn.size()&&i-mn.front().second>=m) mn.pop_front();

while(mx.size()&&t>mx.back().first) mx.pop_back();

while(mn.size()&&t<mn.back().first) mn.pop_back();

mx.emplace_back(t,i),mn.emplace_back(t,i);

if(mx.front().first-mn.front().first==k) q.emplace(l,i);

}

for(int i=n-m+2;i<n;i++)

{

while(mx.size()&&mx.front().second<i) mx.pop_front();

while(mn.size()&&mn.front().second<i) mn.pop_front();

if(mx.front().first-mn.front().first==k) q.emplace(i,n);

}

cout<<q.size()<<'\n';

while(q.size())

cout<<q.front().first<<' '<<q.front().second<<'\n',q.pop();

}