kmjp's blog

競技プログラミング参加記です

square869120Contest #2 : H - Counting 1's

最終問題にしては易しい。
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;
		
		}
	}
}

まとめ

今回難易度順じゃなかったのかな?