うーむ、これは解けてもよかったな。
http://codeforces.com/contest/1076/problem/G
問題
K要素の正整数列Bを用いて、2人で行うゲームを考える。
数列長に対応したK個のマスが並んでおり、初期状態でコマが1番目のマスにおかれる。この際B[0]はデクリメントされる。
以降、両者交互に以下の手順を行う。
定数Mが与えられているとする。
今コマがi番目のマスにある場合、[i,min(i+M,K)]マスのいずれかに移動する。
ただし移動先のマスをjとしたときB[j-1]が正でなければ移動できず、かつ移動先でB[j-1]はデクリメントされる。
自分のターンで移動できなくなったら負けである。
ここで、N要素の整数列AとMが与えられる。
以下のクエリに答えよ。
- Aのある部分列A[L..R]に定数Dを加算する。
- Aのある部分列A[L..R]に対し、上記ゲームを行った場合、両者最適手を取った場合の勝者を答える。
解法
各要素の値の詳細な値は関係なく、いずれも正であること以外には偶奇だけわかっていればよい。
自分の番が回ってきたとき、対応する要素が偶数の場合、その場にとどまる選択肢は取れない(相手が同じ選択肢を取ると、いずれ自分B[j]=0の状態で自分の番が回ってくる)。
よって[i+1,min(i+M,K)]のいずれかに移動しなければならない。
奇数の場合は、その場にとどまってもよいので[i,min(i+M,K)]のどこかに移動すればよい。
よって、自分の番が回ってきたとき勝てるかどうかは、その時点のB[j]の偶奇と[(i+1),min(i+M,K)]のうち必敗な状態があるかどうかで決まる。
必敗な状態があれば、そこに移動させれば相手が負ける、すなわち自分が勝つ。
あとはSegTreeないし平方分割で解く。
以下のコードは平方分割である。分割数をかなり手直ししないとTLEするので注意。
平方分割した各ブロックに対し、その右側M要素の必勝・必敗の組み合わせ2^M通りのbitmaskに対して、ブロック内左端M要素の勝ち負けのbitmaskを返すテーブルを持っておき、前者のクエリ毎に更新する。
前者のクエリはDが偶数なら何もしないと同義で、奇数だと部分列の内容を0/1反転することに対応する。
よって、各ブロック事前に反転後の状態に対するテーブルと、反転の有無を覚えておけば前者のクエリを高速に処理できる。
int N,Q,M; const int DI=50; int A[300000]; int dp[10000][2][32]; int S[10000]; inline int nex(int cur,int a) { if(a==0) cur = (cur<<1) | 1; else cur = (cur<<1) | (cur!=(1<<M)-1); return cur&((1<<M)-1); } int update(int v,int l,int r) { int i,t; if(S[v]) { FOR(i,DI) A[DI*v+i]^=1; S[v]=0; } for(i=l;i<r;i++) A[DI*v+i]^=1; for(int mask=0;mask<1<<M;mask++) { FOR(t,2) { int cur=mask; for(i=DI-1;i>=0;i--) cur=nex(cur,A[DI*v+i]^t); dp[v][t][mask]=cur; } } } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>Q; FOR(i,N) { ll l; cin>>l; A[i]=l%2; } FOR(i,250000/DI) update(i,0,0); while(Q--) { int T,L,R; cin>>T>>L>>R; L--; if(T==1) { ll l; cin>>l; if(l%2==0) continue; while(L/DI != R/DI) { if(L%DI==0) { S[L/DI]^=1; L+=DI; } else { update(L/DI,L%DI,DI); L+=DI-(L%DI); } } update(L/DI,L%DI,R%DI); } else { int cur=(1<<M)-1; while(R>L && R%DI!=0) R--, cur=nex(cur,A[R]^S[R/DI]); while(R>=L+DI) R-=DI, cur=dp[R/DI][S[R/DI]][cur]; while(R>L) R--, cur=nex(cur,A[R]^S[R/DI]); cout<<2-(cur&1)<<endl; } } }
まとめ
うーん、SegTreeにせよ平方分割にせよ、これは解いておきたかった。