GCJなんで問題文がこんなに長いの…?
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051706/0000000000122838
問題
N要素の整数列C,Dと非負整数Kが与えられる。
区間[L,R]のうち、max(C[L..R])とmax(D[L..R])の差の絶対値がK以下となるものは何通りか。
解法
こういう数え上げは、片方を降順に見ていきながら、その要素を必ず含む区間において、左右をどこまで伸ばせるか見ていくとよいことが多い。
今回はCを降順に処理していこう。
C[X]およびC[Y]はすでに処理済みで、区間[X+1,Y-1]においてC[Z]が最大値とする。
この時、左端Lと右端Rをどこまで伸ばせるか考える。
手順としては、max(D[L..R])<=C[cur]+Kなものを数え上げた後、max(D[L..R])
int N; int K; pair<int,int> P[101010]; int D[101010]; template<class V,int NV> class SegTree_1 { public: vector<V> val; static V const def=0; V comp(V l,V r){ return max(l,r);}; void init(){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]=comp(v,val[entry]); while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]); } }; SegTree_1<int,1<<19> st; void solve(int _loop) { int f,i,j,k,l,x,y; st.init(); cin>>N>>K; set<int> invalid; invalid.insert(0); invalid.insert(N+1); ll ret=0; FOR(i,N) { P[i].second=i+1; cin>>P[i].first; } FOR(i,N) { cin>>x; st.update(i+1,x); } sort(P,P+N); reverse(P,P+N); FOR(i,N) { int cur=P[i].second; auto it=invalid.lower_bound(cur); int R=*it-1; it--; int L=*it+1; invalid.insert(cur); ll maL=cur+1,maR=cur-1; ll miL=cur+1,miR=cur-1; for(j=19;j>=0;j--) { if(maL-(1<<j)>=L && st.getval(maL-(1<<j),cur+1)<=P[i].first+K) maL-=1<<j; if(maR+(1<<j)<=R && st.getval(cur,maR+(1<<j)+1)<=P[i].first+K) maR+=1<<j; if(miL-(1<<j)>=L && st.getval(miL-(1<<j),cur+1)<P[i].first-K) miL-=1<<j; if(miR+(1<<j)<=R && st.getval(cur,miR+(1<<j)+1)<P[i].first-K) miR+=1<<j; } ret+=(cur+1-maL)*(maR+1-cur)-(cur+1-miL)*(miR+1-cur); } _P("Case #%d: %lld\n",_loop,ret); }
まとめ
なんかCodeforcesっぽい問題。