こういう問題1ずれが起きそうで怖い。
http://codeforces.com/contest/689/problem/D
問題
N要素の2つの数列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; }
まとめ
細かいミスを繰り返した。
サンプルテストケースが弱くて辛い。