なんだこりゃ。
http://codeforces.com/contest/915/problem/E
問題
N日間の授業日に対し、以下のクエリが順次与えられる。
適宜授業日の日数を答えよ。
- ある区間内の日がすべて授業日になる
- ある区間内の日がすべて授業日が解除される
解法
座標圧縮したのち、区間更新・区間和を取るSegTreeを使うだけ。
区間の更新と言っても、その区間を和を取る対称かどうかの2値で管理する。
int N,Q; int L[303030],R[303030],K[303030]; vector<int> C; static ll const def=0; template<class V,int NV> class SegTree_3 { public: vector<V> base, tot; SegTree_3(){ int i; base.resize(NV*2,0); tot.resize(NV*2,0); }; void update(int x,int y, V v,int l=0,int r=NV,int k=1) { if(l>=r) return; if(x<=l && r<=y) { if(v==0) tot[k]=0; else tot[k]=base[k]; } else if(l < y && x < r) { if(tot[k]==0) { tot[2*k]=tot[2*k+1]=0; } else if(tot[k]==base[k]) { tot[2*k]=base[2*k]; tot[2*k+1]=base[2*k+1]; } update(x,y,v,l,(l+r)/2,k*2); update(x,y,v,(l+r)/2,r,k*2+1); tot[k]=tot[2*k]+tot[2*k+1]; } } }; SegTree_3<int,1<<20> st; void solve() { int i,j,k,l,r,x,y; string s; scanf("%d%d",&N,&Q); Q++; C.push_back(1); C.push_back(N+1); FOR(i,Q) { if(i==0) { L[0]=1,R[0]=N,K[0]=2; } else { scanf("%d%d%d",&L[i],&R[i],&K[i]); } R[i]++; C.push_back(L[i]); C.push_back(R[i]); K[i]--; } sort(ALL(C)); C.erase(unique(ALL(C)),C.end()); FOR(i,C.size()-1) st.base[i+(1<<20)]=C[i+1]-C[i]; for(i=(1<<20)-1;i>=1;i--) st.base[i]=st.base[2*i]+st.base[2*i+1]; FOR(i,Q) { x=lower_bound(ALL(C),L[i])-C.begin(); y=lower_bound(ALL(C),R[i])-C.begin(); st.update(x,y,K[i]); if(i) _P("%d\n",st.tot[1]); } }
まとめ
いまいち意図がわからない問題。