問題一覧 > 通常問題

No.2002 Range Swap Query

レベル : / AI推定難易度 : 1850 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 50
作問者 : 👑 to-omer / テスター : souta-1326 ygussany
お気に入りにしたユーザー ProblemId : 7715 / 自分の提出
問題文最終更新日: 2022-07-08 18:38:41
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 351 (順位表) の他の問題:

Problem Statement

There is a sequence $P=(1,2,\dots,N)$ of length $N$.
There are also $K$ operations, where operation $i$ swaps $P_{A_i}$ and $P_{B_i}$.
For each $j=1,2,\dots,Q$, find $P_{X_j}$ after performing operations $L_j,L_j+1,\dots,R_{j}$ in this order.
Note that $P=(1,2,\dots,N)$ before the operations start for every $j$.

Constraints

  • All input values are integers.
  • $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)$

Input

$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$

Output

Output $Q$ lines.
On the $j$-th line, output $P_{X_j}$ after performing operations $L_j,L_j+1,\dots,R_{j}$ in this order.

Sample

Sample 1
Input
3 3 2
1 2
1 3
2 3
2 2 1
1 3 2
Output
3
2
  • $j=1$: Performing only operation $2$ changes the sequence as $(\mathbf{1},2,\mathbf{3})\to(3,2,1)$, so output $P_1=3$.
  • $j=2$: Performing operations $1,2,3$ in order changes the sequence as $(\mathbf{1},\mathbf{2},3)\to(\mathbf{2},1,\mathbf{3})\to(3,\mathbf{1},\mathbf{2})\to(3,2,1)$, so output $P_2=2$.
Sample 2
Input
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
Output
3
1
5
3
2
4
2
5

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