No.1024 Children in a Row

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 9
作問者 : chocoruskchocorusk / テスター : CinnamorollCinnamoroll
2 ProblemId : 4034 / 出題時の順位表
問題文最終更新日: 2020-04-11 00:17:44

問題文

$1, 2, \ldots , N$ の番号がついた $N$ 人の子どもがこの順に前から一列に並んでいます。$M$ 回の移動が行われようとしています。$i$ 回目 ($1\leq i\leq M$) の移動では、人 $a_i$ が人 $b_i$ の真後ろに移動します (人 $b_i$ の後ろに人がいる場合は割り込みます)。

各 $i$ ($1\leq i\leq M$) に対し、$M$ 回の移動のうち $i$ 回目のみを飛ばして順に行った場合の最終的な列における前から $k_i$ 番目の人の番号を求めてください。

入力

$N\ M$
$a_1\ b_1\ k_1$
$a_2\ b_2\ k_2$
$:$
$a_M\ b_M\ k_M$

  • $2\leq N, M\leq 2\times 10^5$
  • $1\leq a_i, b_i, k_i\leq N$
  • $a_i\neq b_i$
  • 入力はすべて整数である。

出力

$M$ 行出力せよ。$i$ 行目 ($1\leq i\leq M$) には、$M$ 回の移動のうち $i$ 回目のみを飛ばして順に行った場合の最終的な列における前から $k_i$ 番目の人の番号を出力せよ。

サンプル

サンプル1
入力
4 3
1 2 3
4 2 1
3 1 4
出力
2
2
3

  • $1$ 回目の移動を飛ばして $2$, $3$ 回目の移動のみを行った場合、列は $(1, 2, 3, 4)\to (1, 2, 4, 3)\to (1, 3, 2, 4)$ と変化します。この最終的な列における前から $3$ 番目の人の番号は $2$ です。
  • $2$ 回目の移動を飛ばして $1$, $3$ 回目の移動のみを行った場合、列は $(1, 2, 3, 4)\to (2, 1, 3, 4)\to (2, 1, 3, 4)$ と変化します。この最終的な列における前から $1$ 番目の人の番号は $2$ です。
  • $3$ 回目の移動を飛ばして $1$, $2$ 回目の移動のみを行った場合、列は $(1, 2, 3, 4)\to (2, 1, 3, 4)\to (2, 4, 1, 3)$ と変化します。この最終的な列における前から $4$ 番目の人の番号は $3$ です。

サンプル2
入力
2 3
2 1 2
2 1 1
1 2 1
出力
1
2
1

サンプル3
入力
9 8
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9
3 2 3
8 4 6
2 6 4
出力
1
9
1
7
9
5
3
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。