yukicoder : No.2002 Range Swap Query

これは本番意外とすんなり解けたな。
https://yukicoder.me/problems/no/2002

問題

初期状態で整数列P=(1,2,...,N)がある。
ここでK種類の操作があり、各操作はP中のA[i]番目の要素とB[i]番目の要素を入れ替えるものである。

以下のクエリに順次答えよ。

• 各クエリは操作の区間[L,R]とインデックスXで構成される。Pに対しL番目からR番目までの処理を行ったとき、P[X]の値を求めよ

解法

以下のように考える。

• 1番目からR番目の処理を逆向きに巻き戻し、元々どこの位置の値が、数列のX番目に来るかを逆算する。
• その後、1番目から(L-1)番目の処理を行い、X番目の要素がどこに行くかを求める。それがY番目に行くのであれば、このクエリの解はY。

これを各クエリ並行して行う。
後者の処理は、まず時間順に各処理を行い、元の要素がある処理まで行った時点でどこに移動しているかを、入れ替えたタイミングと合わせて配列で持とう。
そうすれば、二分探索をすることで(L-1)番目までの処理を行ったとき、X番目の要素がどこに移動するかを求めることができる。

前者については、Rの小さい順に処理を行い、逆向きに巻き戻すときのテーブルを保持していけばよい。

int N,K,Q;
int A[202020],B[202020];
vector<pair<int,int>> pos[404040];
int P[404040];
int L[404040],R[404040],X[404040];
vector<int> ev[404040];
int ret[404040];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>Q;
	FOR(i,N) {
		pos[i]={{0,i}};
		P[i]=i;
	}
	
	for(i=1;i<=K;i++) {
		cin>>A[i]>>B[i];
		A[i]--;
		B[i]--;
		swap(P[A[i]],P[B[i]]);
		pos[P[A[i]]].push_back({i,A[i]});
		pos[P[B[i]]].push_back({i,B[i]});
	}
	FOR(i,Q) {
		cin>>L[i]>>R[i]>>X[i];
		X[i]--;
		ev[R[i]].push_back(i);
	}
	FOR(i,N) P[i]=i;
	for(i=1;i<=K;i++) {
		swap(P[A[i]],P[B[i]]);
		FORR(e,ev[i]) {
			y=P[X[e]];
			auto it=lower_bound(ALL(pos[y]),make_pair(L[e],0));
			it--;
			ret[e]=it->second+1;
		}
	}
	
	FOR(i,Q) cout<<ret[i]<<endl;
}

まとめ

もう2000問超えてるんだな。