Codeforces ECR #107 : G. Chips on a Board

これは変則的なNIM。
https://codeforces.com/contest/1511/problem/G

問題

N*Mのグリッドがあり、各行に1個ずつチップが置かれたマスがある。
それぞれそのマスの位置は指定されている。

以下のクエリに順次答えよ。
グリッドのうち、L列目からR列目だけを残したものを考える。
このグリッドを使い、以下の二人制のターン制ゲームを行う。
各自のターンでは、チップを1つ選択して1マス以上左の列に移動する。
もし自分のターンでチップを移動できない場合、負けとなる。
互いに最適手を取る場合、勝者は先手後手いずれかを答える。

解法

個々の問題は明らかにnimである。
L列の位置を走査しながら、各チップに関する左側の空きマス数のxorを取ることを考える。

事前にチップのある列が昇順となるようにソートしておく。
そうすれば、各クエリに対し、ある行の区間のみにチップが存在することになるので、空きマス数のxorをprefix-sumの要領で計算できるようになる。

ここで、列数は高々200000なので、空きマス数は2^18以下である。
そこで、空きマス数を下位9桁と上位9桁で分けて考えよう。

L%512の値に応じ、(空きマス数-L)%512の値のprefix-xorを事前に計算しておこう。
これはO(N*√M)で計算できる。
また、上位9桁はLを走査していく際、各列Lが512変化する間に1回しか変化しない。
こちらのprefix-xorはBITを使い更新していけば。O(N*√(MlogN)))で計算できる。

const int DI=512;

int H,W,Q;
int S[202020],SS[202020];
int L[202020][DI];
int X[202020],Y[202020];

template<class V, int ME> class BIT {
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;}
};
BIT<int,19> bt;
vector<int> cand[DI];
vector<int> ev[202020];
int ret[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(i,H) cin>>S[i];
	sort(S,S+H);

	cin>>Q;
	FOR(i,Q) {
		cin>>X[i]>>Y[i];
		ev[X[i]].push_back(i);
	}
	
	FOR(i,H) {
		FOR(j,DI) {
			L[i+1][j]=L[i][j]^((S[i]+DI-j)%DI);
		}
		SS[i]=(S[i]-1)/DI;
		bt.add(i+1,SS[i]);
		cand[S[i]%DI].push_back(i);
	}
	
	int SL=0;
	for(x=1;x<=W;x++) {
		while(SL<H&&S[SL]<=x) SL++;
		
		FORR(e,ev[x]) {
			y=lower_bound(S,S+H,Y[e]+1)-S;
			
			if(y>SL) {
				ret[e]=((L[y][x%DI]^L[SL][x%DI])>0)||((bt(y)^bt(SL))>0);
			}
			
		}
		
		FORR(c,cand[x%DI]) if(SS[c]) {
			bt.add(c+1,SS[c]);
			SS[c]--;
			bt.add(c+1,SS[c]);
		}
		
	}
	
	FOR(i,Q) {
		if(ret[i]==0) cout<<"B";
		else cout<<"A";
	}
	cout<<endl;
}

まとめ

この平方分割は思い浮かばなかった。