yukicoder : No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ

はてなは半角カタカナ大丈夫かな。
http://yukicoder.me/problems/625

問題

N個の連続したマスがある。
初期状態では各マスは無色である。

ここで、A,B２チームが自チームのカラーでマスを塗りポイントを稼ぐゲームを行う。
ゲーム中では以下のイベントが時系列で発生した。

• 片方のチームが区間[L..R]を自チームのカラーで塗った。(元々塗られた色は上書きされる)
• 区間[L..R]に対しボーナスが発生。区間内で自カラーを塗ったセルが多い方のチームに対し、自カラーのセル分ポイント取得。

また、ゲーム終了後は自カラーで塗られたセルの数だけポイントが入る。
両チームの総得点を求めよ。

解法

チームごとに「各セルが自カラーか否か。また区間内の自カラーで塗られたセル数を数える」という機能を持つ遅延評価SegTreeを持とう。
これが出来れば、あとはどちらのイベントも遅延評価SegTreeで区間を塗ったり数を数えるだけでよい。

この遅延評価SegTreeでは、区間ごとに以下のに２値を管理していく。

• 区間内はすべて自カラーかすべて自カラーでないのいずれか均一の状態であるか、それとも混在しているか。
• 区間内が混在ケースの場合、区間内に自カラーのセルは何個あるか。

遅延評価SegTreeの処理では、既に均一な値を持つと判定された区間内の一部を書き換える場合、一旦その均一な値を半分のサブ区間で伝搬させてから処理を行う点に注意。

template<int NV> class SegTree_Lazy {
public:
	vector<int> val,to;
	SegTree_Lazy(){val.resize(NV*2); to.resize(NV*2);};
	int comp(int l,int r){ return l+r;};

	int getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return 0;
		if(x<=l && r<=y) return to[k];
		x=max(x,l);
		y=min(y,r);
		if(val[k]>=0) return val[k]?(y-x):0;
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}

	void update(int x,int y,int v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]=v;
			to[k]=val[k]?(r-l):0;
		}
		else if(l < y && x < r) {
			if(val[k]!=-1) {
				val[k*2]=val[k*2+1]=val[k];
				to[k*2]=to[k*2+1]=val[k]?(r-l)/2:0;
				val[k]=-1;
			}
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			to[k]=comp(to[k*2],to[k*2+1]);
		}
	}
};

int N,Q;
ll AA,BB;
SegTree_Lazy<1<<20> st[2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	while(Q--) {
		cin>>x>>l>>r;
		
		if(x==0) {
			int a = st[0].getval(l,r+1);
			int b = st[1].getval(l,r+1);
			
			if(a>b) AA+=a;
			if(a<b) BB+=b;
		}
		else {
			st[x-1].update(l,r+1,1);
			st[(x-1)^1].update(l,r+1,0);
		}
	}
	AA+=st[0].getval(0,N);
	BB+=st[1].getval(0,N);
	
	_P("%lld %lld\n",AA,BB);
}

まとめ

遅延評価SegTree系、毎回微妙に遅延評価させる項目が違うのでライブラリ化させず毎回書き直してる気がする。