面倒だけど特段変わった知識が要らない点で★3かな…。
http://yukicoder.me/problems/206
問題
N要素の整数列A[i]が与えられる(A[i]を生成する乱数式・乱数シードが与えられる。)
ここでQ個のクエリが与えられる。
各クエリはs,t,u,vで構成されるので、A[s..t]をA[u..v]に加算せよ。
最終的なA[i]の偶奇を答えよ。
解法
求めるのはA[i]の偶奇なので、複数要素を1整数に畳み込んでビット演算でガリガリやるだけ。
1回のコピー範囲はさほど大きくないので、なんとか間に合う。
ll N,S,X,Y,Z,T,U,V; int Q; ll A[2020000]; ll C[80000]; ll TT[2500]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>S>>X>>Y>>Z; A[0]=S; FOR(i,N) A[i+1]=(X*A[i]+Y)%Z; FOR(i,N) C[i/50]|=(A[i]%2)<<(i%50); cin>>Q; while(Q--) { cin>>S>>T>>U>>V; ll sp=T-S+1; S--,U--; x=S%50; FOR(i,sp/50+2) TT[1+i]=C[S/50+i]; FOR(i,sp/50+2) TT[1+i]=(TT[1+i]>>x) | (((TT[i+2]&((1LL<<x)-1)))<<(50-x)); FOR(i,sp/50+4) { if((i+1)*50<=sp) continue; else if((i+1)*50-sp<=50) TT[i+1]&=(1LL<<(sp%50))-1; else TT[i+1]=0; } x=U%50; for(i=sp/50+2;i>=0;i--) TT[i+1]=((TT[i+1]<<x) | (TT[i]>>(50-x))) & ((1LL<<50)-1); FOR(i,sp/50+2) C[i+U/50] ^= TT[i+1]; } FOR(i,N) _P("%c","EO"[(C[i/50]>>(i%50))&1]); _P("\n"); }
まとめ
昔画像の半透明描画とかでbit演算ガリガリやってたのが活きた。