HourRank18 : C. Max-Min Difference in an Interval

うーん、あと一歩。
https://www.hackerrank.com/contests/hourrank-18/challenges/max-min-difference-in-an-interval

問題

N要素の数列A[i]が与えられる。
max(b,e)はA[b...e]の最大値、min(b,e)はA[b...e]の最小値とする。

ここでQ個のクエリが与えられる。
各クエリは2値Low,Hightからなる。
Low≦max(b,e)-min(b,e)≦Highとなる(b,e)の組み合わせを求めよ。

解法

入力サイズより、O(NQ)程度で答えられることが推測できる。
実際、以下の解法はO(NQ*logN)である。
bを固定したとき、max(b,e)-min(b,e)はeを大きくするほど大きくなる。
よってbを総当たりしつつ、尺取り法をもちいてmax(b,R)-min(b,R)≦Highとなる最大のRとmax(b,L)-min(b,L)＜Lowとなる最大のLを求め、R-Lをb毎に総和を取ればよい。
max/minの算出はmultisetを用いればSegTree等用いる必要はない。

int N,Q;
int A[505050];
int L[2020202],R[2020202];
vector<int> V;
ll cnt[404040];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>A[i];
	
	multiset<int> X,Y;
	FOR(i,Q) {
		cin>>x>>y;
		int L=0,R=0;
		ll ret=0;
		FOR(j,N) {
			while(R<=j) Y.insert(A[R++]);
			while(L<=j) X.insert(A[L++]);
			while(*Y.rbegin()-*Y.begin()<=y && R<N) Y.insert(A[R++]);
			while(*Y.rbegin()-*Y.begin()>y) { Y.erase(Y.find(A[--R]));}
			while(*X.rbegin()-*X.begin()<x && L<N) X.insert(A[L++]);
			while(*X.rbegin()-*X.begin()>=x) { X.erase(X.find(A[--L]));}
			ret+=R-L;
			
			X.erase(X.find(A[j]));
			Y.erase(Y.find(A[j]));
		}
		cout<<ret<<endl;
		
		
		
	}
}

まとめ

気づけばあっさり。