最終問題にしては易しい。
http://s8pc-2.contest.atcoder.jp/tasks/s8pc_2_h
問題
01で構成されたN文字の列がある。
これらに対し以下のQ個のクエリに答えよ。
- 列中、連続区間[L,R)における01を反転する。
- 列中、連続区間[L,R)に1の数を答える。
解法
遅延評価SegTreeで各セグメントの反転の有無を覚えておくだけ。
template<class V,int NV> class SegTree_3 { public: vector<pair<int,int> > val; vector<int> flip; SegTree_3(){ int i; val.resize(NV*2); flip.resize(NV*2); FOR(i,NV) val[i+NV]={1,0}; for(i=NV-1;i>=1;i--) val[i]={val[i*2].first+val[i*2+1].first,val[i*2].second+val[i*2+1].second}; }; pair<int,int> getval(int x,int y,int l=0,int r=NV,int k=1) { if(r<=x || y<=l) return make_pair(0,0); if(x<=l && r<=y) { return (flip[k])?make_pair(val[k].second,val[k].first):val[k]; } auto a=getval(x,y,l,(l+r)/2,k*2); auto b=getval(x,y,(l+r)/2,r,k*2+1); a.first+=b.first; a.second+=b.second; if(flip[k]) swap(a.first,a.second); return a; } 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) { flip[k]^=1; } else if(l < y && x < r) { update(x,y,v,l,(l+r)/2,k*2); update(x,y,v,(l+r)/2,r,k*2+1); val[k] = {0,0}; val[k].first += flip[k*2]?val[k*2].second:val[k*2].first; val[k].second += flip[k*2]?val[k*2].first:val[k*2].second; val[k].first += flip[k*2+1]?val[k*2+1].second:val[k*2+1].first; val[k].second += flip[k*2+1]?val[k*2+1].first:val[k*2+1].second; } } }; SegTree_3<int,1<<20> seg; int N,Q; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>Q; while(Q--) { cin>>i>>x>>y; if(i==1) { seg.update(x,y,0); } else { auto r=seg.getval(x,y); cout<<r.second<<endl; } } }
まとめ
今回難易度順じゃなかったのかな?