2014-01-13

Codeforces #223 Div2 C. Sereja and Prefixes

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;
}

Codeforces #223 Div2 D. Sereja and Tree

23:18 |

深さlevel、左からpos番目のノードに対して posが2の累乗なら左右の子、それ以外なら右の子を持つ最大深さNの木がある。各ノードには空集合が入っている。
以下の２つの命令が計M個くるので処理する問題。
(1) level[i], posL[i]〜posR[i] のノードに入ってる集合に x[i] を追加する
(2) level[i], pos[i] のノードとそのsubtreeの集合の和集合の要素数を印字する
1≦N,M≦7000
1≦x[i]≦10^6

ややこしや
もう寝ようかな
ややこしや

図が完全二分木じゃないのは間違ってる？
よく読んだら２つの子を持つのは2の累乗のときだけ, か...
なのでノード数は 2^7000 とかにはならない。深さ7000の葉の個数は109332個

(1) が来た時
data[i][level][3] = {L, R, X} ... i番目の追加命令では深さlevelに対して L≦pos≦R に X を追加した
と覚えておけば (2) のとき O(MlogM) で答えが出せるからそうしよう
→256MB に入らない

おしまい

あとで

逆に(2)が来た時に全深さに対して pos の範囲を計算しといて追加命令の範囲と共通箇所があればカウント
だとメモリが少なくて済む
なるほど
accepted in practice

int chL[110000]; // L child, 1base
int chR[110000]; // R child, 1base
int rL[7007];
int rR[7007];
int T[7007];
int L[7007];
int R[7007];
int X[7007];

// 109332
int main() {
	ios::sync_with_stdio(false);
	ll N,M;
	ll type,t,v;
	while(cin>>N>>M) {
		int cs=1;
		REP(i, 110000) {
			int ch = (POPCOUNT(i+1)==1) ? 2:1;
			chL[i+1]=ch==2?cs++:-1;
			chR[i+1]=cs++;
		}
		int hints=0;
		REP(i, M) {
			cin>>type;
			if(type==1) {
				cin>>T[hints]>>L[hints]>>R[hints]>>X[hints];
				hints++;
			} else {
				cin>>t>>v;
				REP(j, t) rL[j]=rR[j]=-1;
				rL[t]=rR[t]=v;
				RANGE(j, t, N) {
					rL[j+1]=chL[rL[j]]==-1 ? chR[rL[j]] : chL[rL[j]];
					rR[j+1]=chR[rR[j]];
				}
				map<int, int> ma;
				REP(hi, hints) {
					if(rL[T[hi]]==-1) continue;
					bool in = !(R[hi]<rL[T[hi]] || rR[T[hi]]<L[hi]);
					if(in) ma[X[hi]]=1;
				}
				cout<<ma.size()<<endl;
			}
		}
	}
	
	return 0;
}

kojingharangの日記

2014-01-13

Codeforces #223 Div2 C. Sereja and Prefixes

Codeforces #223 Div2 D. Sereja and Tree