Codeforces #361 Div2 D. Friends and Subsequences

こういう問題1ずれが起きそうで怖い。
http://codeforces.com/contest/689/problem/D

問題

N要素の２つの数列A,Bが与えられる。
N要素中の連続区間[L,R]の取り方はN*(N-1)/2通りある。
その時、max(A[L..R])=min(B[L..R])を満たす[L,R]は何通りあるか。

解法

Lを固定し、Rを増やしていくとmax(A[L..R])は段々大きくなり、min(B[L..R])は小さくなる。
A[L]≦B[L]であれば、max(A[L..R])=min(B[L..R])を満たすRが存在する可能性がある。
よってAに対しRange Maximum Query、Bに対しRange Minumum Queryを処理するSegTreeを持ち、max(A[L..R])=min(B[L..R])を満たす最小・最大のRを二分探索すればよい。
この解法だとO(N*(log^2)N)かかるが、RMQの二分探索をダブリングの要領でもう少し軽量に実装するとO(NlogN)になる。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=-1<<30;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
template<class V,int NV> class SegTree_2 {
public:
	vector<V> val;
	static V const def=1<<30;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_2(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

int N;
int A[202020];
int B[202020];
SegTree_1<int,1<<18> st1;
SegTree_2<int,1<<18> st2;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i], st1.update(i,A[i]);
	FOR(i,N) cin>>B[i], st2.update(i,B[i]);
	
	ll ret=0;
	FOR(i,N) if(A[i]<=B[i]) {
		if(st1.getval(i,N)<st2.getval(i,N)) continue;
		int L=N;
		int R=i;
		for(j=17;j>=0;j--) {
			if(L-(1<<j)>=i && st1.getval(i,L-(1<<j))>=st2.getval(i,L-(1<<j))) L-=1<<j;
			if(R+(1<<j)<=N && st1.getval(i,R+(1<<j))<=st2.getval(i,R+(1<<j))) R+=1<<j;
		}
		if(L<=R) ret += R-L+1;
	}
	cout<<ret<<endl;
	
}

まとめ

細かいミスを繰り返した。
サンプルテストケースが弱くて辛い。