yukicoder : No.961 Vibrant Fillumination

割と思いつくのに手間取った。
https://yukicoder.me/problems/no/961

問題

グリッド上にいくつかの色の矩形のガラスを置く。
複数のガラスを重ねてもよく、同色のガラスは複数枚重ねても色が変わらない。

ガラスの位置・色に加え、グリッド上の位置を示すクエリが与えられる。
その位置に重なる全色に対応するハッシュ値のxorを求めよ。

解法

列方向に平面走査することを考える。

その際、平方分割を用いる。
まずガラスの色の種類毎に行方向に座標圧縮しよう。
ユニークな行数が十分に少ない(O(√N)程度)の物をまとめて扱う。

これらのガラスについて、区間のxorを取るBITを用いてまとめて平面走査しよう。
各ガラスについて、圧縮済みの座標において更新される行数はO(√N)個程度なので、各行の重なったガラス枚数が0-1の間で行き来する際にBITの値を更新する。
ガラスの両端を走査する際1枚あたりO(√NlogN)程度で状態を更新できる。
クエリも同時に平面走査し、重なった色のxorの値を取ろう。

圧縮後のユニークな行数が多いガラスについては、色ごとに処理する。
今度は各行におけるガラスの重なり枚数をBITで管理しよう。
同じく列方向に平面走査し、クエリ処理時に対象の行が1枚以上ガラスが重なっているか見ていけばよい。

int N;
ll H[505050];
int X1[505050],Y1[505050];
int X2[505050],Y2[505050];
vector<ll> Ys[101010];
int C[505050];

int Q;
int QX[101010],QY[101010];
ll ret[101010];
vector<int> add[101010],del[101010],query[101010];
int cnt[101010];

template<class V, int ME> class BITxor {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s^=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]^=v,e+=e&-e;}
};
BITxor<ll,20> btx;

template<class V, int ME> class BITsum {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BITsum<int,20> bts;

int id[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>H[i];
	FOR(i,N) {
		cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i]>>C[i];
		C[i]--;
		Ys[C[i]].push_back(Y1[i]);
		Ys[C[i]].push_back(Y2[i]);
		add[X1[i]].push_back(i);
		del[X2[i]].push_back(i);
	}
	
	FOR(i,N) {
		sort(ALL(Ys[i]));
		Ys[i].erase(unique(ALL(Ys[i])),Ys[i].end());
		id[i+1]=id[i]+Ys[i].size();
	}
	FOR(i,N) {
		Y1[i]=lower_bound(ALL(Ys[C[i]]),Y1[i])-Ys[C[i]].begin();
		Y2[i]=lower_bound(ALL(Ys[C[i]]),Y2[i])-Ys[C[i]].begin();
	}
	cin>>Q;
	FOR(i,Q) {
		cin>>QX[i]>>QY[i];
		query[QX[i]].push_back(i);
	}
	FOR(x,101000) {
		FORR(a,add[x]) if(Ys[C[a]].size()<=200) {
			for(y=Y1[a];y<Y2[a];y++) if(++cnt[y+id[C[a]]]==1) {
				btx.add(Ys[C[a]][y],H[C[a]]);
				btx.add(Ys[C[a]][y+1],H[C[a]]);
			}
		}
		FORR(a,del[x]) if(Ys[C[a]].size()<=200) {
			for(y=Y1[a];y<Y2[a];y++) if(--cnt[y+id[C[a]]]==0) {
				btx.add(Ys[C[a]][y],H[C[a]]);
				btx.add(Ys[C[a]][y+1],H[C[a]]);
			}
		}
		FORR(q,query[x]) ret[q]=btx(QY[q]);
	}
	FOR(i,101000) if(Ys[i].size()>200) {
		FOR(x,101000) {
			FORR(a,add[x]) if(C[a]==i) {
				bts.add(Ys[i][Y1[a]],1);
				bts.add(Ys[i][Y2[a]],-1);
			}
			FORR(a,del[x]) if(C[a]==i) {
				bts.add(Ys[i][Y1[a]],-1);
				bts.add(Ys[i][Y2[a]],1);
			}
			FORR(q,query[x]) if(bts(QY[q])>0) ret[q]^=H[i];
		}
		
	}
	FOR(i,Q) cout<<ret[i]<<endl;
}

まとめ

これも「orを取るので平面走査の方が扱いやすい」タイプかな。