Codeforces #223 Div2 C. Sereja and Prefixes

2014-01-13

23:18 |

空の列から始めて、(1)数字 X[i] を末尾に追記または (2) 先頭から L[i] 文字を C[i] 回末尾に追記の操作を合計 M 回する。
出来上がった列の I[i] 番目の数字を N 個出力する問題。
1≦X[i], L[i], I[i], N, M≦100,000
1≦C[i]≦10,000

i 回目の操作後の列の長さ len[i] を覚えておく
len の I[i] 以上の最初のインデックス d を2分探索で求めて、I[i] がどの操作で生まれたものかを特定する。
(1) なら追記した数字 X[d]、(2) なら先頭の (I[i]-1-len[d-1]) % L[d-1] の位置の文字。
コピー元の長さ≦100,000なのでそこまでは全部作って覚えておく

accepted

ll p[100010][3];
ll w[100010];
ll len[100010];
int main() {
	ios::sync_with_stdio(false);
	ll N,M;
	while(cin>>M) {
		len[0]=0;
		REP(i, M) {
			cin>>p[i][0];
			if(p[i][0]==1) {
				cin>>p[i][1];
				len[i+1] = len[i]+1;
				if(len[i]<100000) w[len[i]] = p[i][1];
			}
			if(p[i][0]==2) {
				cin>>p[i][1]>>p[i][2];
				len[i+1] = len[i]+p[i][1]*p[i][2];
				for(int j=0;j<p[i][1]*p[i][2] && len[i]+j<100000;j++) {
					w[len[i]+j]=w[j%p[i][1]];
				}
			}
		}
		cin>>N;
		VI ans(N);
		REP(i, N) {
			ll idx;
			cin>>idx;
			int d = distance(&len[0], lower_bound(&len[0], &len[M+1], idx));
			if(p[d-1][0]==1) {
				assert(idx==len[d]);
				ans[i] = p[d-1][1];
			} else {
				int j = (idx-1-len[d-1]) % p[d-1][1];
				ans[i] = w[j];
			}
		}
		
		REP(i, N) {
			if(i) cout<<" ";
			cout<<ans[i];
		}
		cout<<endl;
	}
	
	return 0;
}