問題一覧 > 通常問題

No.2002 Range Swap Query

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 34
作問者 : to-omerto-omer / テスター : souta-1326souta-1326 👑 ygussanyygussany
4 ProblemId : 7715 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-08 18:38:41

問題文

長さ $N$ の数列 $P=(1,2,\dots,N)$ があります。
また、 $K$ 個の操作があり、操作 $i$ は $P_{A_i}$ と $P_{B_i}$ を入れ替える操作です。
各 $j=1,2,\dots,Q$ について、操作 $L_j,L_j+1,\dots,R_{j}$ をこの順に行ったときの $P_{X_j}$ を求めてください。
ただし、どの $j$ でも操作の開始前は $P=(1,2,\dots,N)$ であることに注意してください。

制約

  • 入力は全て整数である。
  • $2\le N\le 4\times 10^{5}$
  • $1\le K\le 2\times 10^{5}$
  • $1\le Q\le 2\times 10^{5}$
  • $1\le A_i<B_i\le N\ (1\le i\le K)$
  • $1\le L_j\le R_j\le K\ (1\le j\le Q)$
  • $1\le X_j\le N\ (1\le j\le Q)$

入力

$N$ $K$ $Q$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_K$ $B_K$
$L_1$ $R_1$ $X_1$
$L_2$ $R_2$ $X_2$
$\vdots$
$L_Q$ $R_Q$ $X_Q$

出力

$Q$ 行出力してください。
$j$ 行目には操作 $L_j,L_j+1,\dots,R_{j}$ をこの順に行ったときの $P_{X_j}$ を出力してください。

サンプル

サンプル1
入力
3 3 2
1 2
1 3
2 3
2 2 1
1 3 2
出力
3
2
  • $j=1$ :操作 $2$ のみを行うと、 $(\mathbf{1},2,\mathbf{3})\to(3,2,1)$ と変化するので、$P_1=3$ を出力します。
  • $j=2$ :操作 $1,2,3$ を順に行うと、 $(\mathbf{1},\mathbf{2},3)\to(\mathbf{2},1,\mathbf{3})\to(3,\mathbf{1},\mathbf{2})\to(3,2,1)$ と変化するので、$P_2=2$ を出力します。
サンプル2
入力
6 9 8
1 5
1 4
4 5
1 4
4 5
1 4
4 5
1 3
4 5
4 6 3
5 7 5
3 8 5
4 6 3
3 6 2
8 9 5
3 6 2
1 4 5
出力
3
1
5
3
2
4
2
5

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