kmjp's blog

競技プログラミング参加記です

yukicoder : No.142 単なる配列の操作に関する実装問題

面倒だけど特段変わった知識が要らない点で★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演算ガリガリやってたのが活きた。