データ構造の問題． 愚直に移動を実装していてはTLE. コンテナ毎について， 下に何があるか，上に何があるか を記録しておく． 切れ目とつなぎ目だけ更新すれば良いので \(O(Q)\)
実装
今回の問題では，上に何があるかは記録しなくてもよい，
また，机とコンテナを区別するために， 机 \(i\) を \(-i\)として記録して， コンテナ \(j\) を \(j\)として記録する． \(-i\) を使うため 0 が出てくると困るので， 1-indexed とする．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m, k, q;
cin >> n >> q;
// 1-ind
vll pre(n+1);
// vll ne(n+1);
vll top(n+1);
rep1(i,n){
top[i] = i;
pre[i] = -i;
// ne[i] = -INFL;
}
rep(qi,q){
ll f,t,x; cin >> f >> t >> x;
ll tt = top[t];
top[t] = top[f];
top[f] = pre[x];
pre[x] = tt;
// ne[tt] = x;
}
vll ans(n+1);
rep1(i,n){
ll x = top[i];
while(x > 0){
ans[x] = i;
x = pre[x];
}
}
rep1(i,n){
cout << ans[i] << endl;
}
return 0;
}
