yukicoder : No.1997 X Lighting

これは割とすんなり。
https://yukicoder.me/problems/no/1997

問題

N*Nのグリッド上の各セルに電球があり、初期状態で全電球消灯している。
ここで次のクエリが与えられる。

• セル(x,y)が指定される。セル(x,y)及び、そこから斜め45度の位置にあるセル上の電球は(消灯していたら)全部点灯する。

最終的に点灯する電球は何通りか。

解法

セル(x,y)が指定されると、セル(a,b)が点灯する条件は

• x+y=a+b
• x-y=a-b

のいずれかである。
言い換えると、x+yが一致する複数のクエリは1回しか効果がないし、x-yが一致する複数のクエリは1回しか効果がない。
よって、まず各クエリに対しP=x+y, Q=x-yとしてそれぞれ個別にP,Qの集合を考える。

各Pに対応して点灯する電球の和と、各Qに対応して点灯す点灯させる電球の和から、P,Q両方で点灯される電球の数を引けば解となる。
前2つはP,Qを総当たりしながら計算すれば求められる。
次に、Pを総当たりしながら、Pに対応して点灯されるQが何通りあるかを考える。
この時、PとQのパリティは一緒である必要があり、その中でPに対しQはある区間が該当する。(両方で点灯される電球がN*Nのグリッド内でなければならないため)

よってQをパリティ別に昇順列にしておけば、lower_boundでPごとに対し該当するQの個数を高速に計算できる。

ll N;
ll M;
set<ll> A,B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		ll X,Y;
		cin>>X>>Y;
		X--,Y--;
		A.insert(X+Y);
		B.insert(X-Y);
	}
	vector<ll> Bs[2];
	
	ll ret=0;
	FORR(v,B) {
		ret+=N-abs(v);
		Bs[abs(v)%2].push_back(v);
	}
	FORR(v,A) {
		if(v<N) {
			ret+=v+1;
			ret-=lower_bound(ALL(Bs[v%2]),v+1)-lower_bound(ALL(Bs[v%2]),-v);
		}
		else {
			ret+=2*N-1-v;
			ll w=2*N-2-v;
			ret-=lower_bound(ALL(Bs[v%2]),w+1)-lower_bound(ALL(Bs[v%2]),-w);
		}
	}
	cout<<ret<<endl;
}

まとめ

この類の問題で、オンオフ切り替えではなく、オンになりっぱなしというのは珍しいかも？