Croc Champ 2013 - Round 1 : E. Copying Data

さて最終問題。これも本番に解けて良かった。
http://codeforces.com/contest/292/problem/E

問題

２つの整数値配列A,Bが与えられる。
そこに与えられる以下のクエリを処理せよ。

1. X,Y,Lが与えられるので、A[X]～A[X+L-1]をB[Y]～B[Y+L-1]にコピー
2. Xが与えられるので、B[X]を返す

解法

BITを使って、Bの各要素がどのクエリの時の値を保持するか記憶すればよい。

手元のBITライブラリが各要素の累積値を持つものだったので、クエリの値を持つよう書き直した。

int N,M;
int A[100001];
int B[100001];
const int BITL=19;
typedef pair<int,int> rec ;
rec P[1<<BITL];

void update(int cur,int L,int R,rec p) {
	int bl=0;
	if(L==R) return;
	while(cur>=1<<(bl+1)) bl++;
	int tl=(cur-(1<<bl))<<(BITL-bl-1);
	int tr=(cur-(1<<bl)+1)<<(BITL-bl-1);
	int tm=(tl+tr)/2;
	
	if(tl==L && tr==R) {
		P[cur]=p;
	}
	else {
		if(P[cur].first!=-2) {
			update((1<<(bl+1))+(tl>>(BITL-bl-2)),tl,tm,P[cur]);
			update((1<<(bl+1))+(tm>>(BITL-bl-2)),tm,tr,P[cur]);
		}
		P[cur]=make_pair(-2,0);
		if(L<tm) update((1<<(bl+1))+(tl>>(BITL-bl-2)),L,min(tm,R),p);
		if(R>=tm) update((1<<(bl+1))+(tm>>(BITL-bl-2)),max(L,tm),R,p);
	}
}
void update(int L,int R,rec p) { update(1,L,R,p);}

pair<int,int> val(int entry) {
	int i;
	rec p;
	FOR(i,BITL) {
		p=P[(1<<i)+(entry>>(BITL-i-1))];
		if(p.first!=-2) return p;
	}
	return make_pair(-1,0);
}

void solve() {
	int f,r,i,j,k,l,x,y;
	int ma=0;
	
	GET2(&N,&M);
	FOR(i,N) A[i]=GETi();
	FOR(i,N) B[i]=GETi();
	FOR(i,1<<BITL) P[i]=make_pair(-2,0);
	FOR(i,N) update(i,i+1,make_pair(-1,0));
	
	FOR(i,M) {
		j=GETi();
		if(j==1) {
			x=GETi()-1;
			y=GETi()-1;
			l=GETi();
			update(y,y+l,make_pair(x,y));
			/*
			FOR(j,N) {
				rec p = val(j);
				_P("(%d,%d) ",p.first,p.second);
			}
			_P("\n");
			*/
		}
		else {
			k=GETi()-1;
			rec p = val(k);
			//_P("%d %d %d\n",k,p.first,p.second);
			
			if(p.first==-1) _P("%d\n",B[k]);
			else _P("%d\n",A[p.first+(k-p.second)]);
		}
	}
	
	return;
}

まとめ

これ、クエリ情報としてXとYのペアを覚えておくようにしたけど、考えたらクエリの番号だけ覚え解けばペアの処理をしなくてよくて楽だったな。

今回は問題読み落としやらデータ構造選択のポカミスなど、スコア・時間の小さなロスを積み重ねてしまってもったいなかった。
時間切れとはいえ全部自力で解けたし、Round1抜けたしまぁ上出来だけどね。