Codeforces #368 Div2 E. Garlands

なんか前回と似ている。
http://codeforces.com/contest/707/problem/E

問題

N*Mのグリッドを考える。
一部のセルには、電球の列がある。
各セルは最大で１つの電球しか含まない。また、列を構成する電球群は、隣同士の電球が隣接するセルにあることが分かっている。

各電球には明るさが設定されているとする。
以下のクエリを順次処理せよ。

• 指定したマスにある電球及びその電球と同一の列の電球をすべて消す。
• 指定したマスにある電球及びその電球と同一の列の電球をすべて点ける。
• 矩形が指定されるので、矩形内にある点いている電球の明るさの総和を答える。

解法

前回CF367のEを解いていると、答えはほぼ同じ。
Codeforces #367 Div2 E. Working routine - kmjp's blog

各電球列に対し、累積和を求めておこう。
次に、各電球列の端が矩形の内外どちらかにあるか判定する。
端が内部にあり、かつその電球列が点いているなら、その電球列の明るさの総和を答えに加算しておこう。

次に、矩形の周辺部をぐるっと走査し、電球列が矩形の境界を跨いでいないか判定する。
跨いでいる場合、電球列の後ろ側が外にあるならその分の明るさの総和を引き、後ろ側が内部にあるなら足していけば良い。

int K,Q;
int B[2020][2020];
int I[2020][2020];
int L[2020];
int X[2020][2020];
int Y[2020][2020];
int W[2020][2020];
ll S[2020][2020];
int off[2020];
char C[20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d",&x,&y,&K);
	MINUS(B);
	FOR(i,K) {
		scanf("%d",&L[i]);
		FOR(j,L[i]) {
			scanf("%d%d%d",&X[i][j],&Y[i][j],&W[i][j]);
			B[Y[i][j]][X[i][j]]=i;
			I[Y[i][j]][X[i][j]]=j;
			S[i][j+1]=S[i][j]+W[i][j];
		}
	}
	scanf("%d",&Q);
	while(Q--) {
		int x1,x2,y1,y2;
		scanf("%s %d",C,&x1);
		if(C[0]=='S') off[x1-1] ^= 1;
		else {
			scanf("%d%d%d",&y1,&x2,&y2);
			ll tot=0;
			
			FOR(i,K) if(off[i]==0) {
				if(X[i][L[i]-1]>=x1 && X[i][L[i]-1]<=x2 && 
				   Y[i][L[i]-1]>=y1 && Y[i][L[i]-1]<=y2) tot += S[i][L[i]];
			}
			for(x=x1;x<=x2;x++) {
				if(B[y1][x]>=0 && off[B[y1][x]]==0 && B[y1-1][x]==B[y1][x]) {
					if(I[y1-1][x]==I[y1][x]-1) tot -= S[B[y1][x]][I[y1][x]];
					if(I[y1-1][x]==I[y1][x]+1) tot += S[B[y1][x]][I[y1][x]+1];
				}
				if(B[y2][x]>=0 && off[B[y2][x]]==0 && B[y2+1][x]==B[y2][x]) {
					if(I[y2+1][x]==I[y2][x]-1) tot -= S[B[y2][x]][I[y2][x]];
					if(I[y2+1][x]==I[y2][x]+1) tot += S[B[y2][x]][I[y2][x]+1];
				}
			}
			for(y=y1;y<=y2;y++) {
				if(B[y][x1]>=0 && off[B[y][x1]]==0 && B[y][x1-1]==B[y][x1]) {
					if(I[y][x1-1]==I[y][x1]-1) tot -= S[B[y][x1]][I[y][x1]];
					if(I[y][x1-1]==I[y][x1]+1) tot += S[B[y][x1]][I[y][x1]+1];
				}
				if(B[y][x2]>=0 && off[B[y][x2]]==0 && B[y][x2+1]==B[y][x2]) {
					if(I[y][x2+1]==I[y][x2]-1) tot -= S[B[y][x2]][I[y][x2]];
					if(I[y][x2+1]==I[y][x2]+1) tot += S[B[y][x2]][I[y][x2]+1];
				}
			}
			
			cout<<tot<<endl;
		}
	}
}

まとめ

367,368と２連続似たテクが出てきたので、さすがに覚えそう。