수열과 쿼리 2025

시간 제한1초메모리 제한1024 MB

요약

배열에서 값 x를 모두 y로 바꾸는 갱신과 특정 위치의 값을 묻는 질의를 처리한다.

난이도: 보통10점 중 7점
유형: 유니온 파인드, 해시맵, 구현
정답자: 아직 제출이 없습니다

문제

길이가 $N$ 이고 정수로 구성된 수열 $A\_1$ , $A\_2$ , $\dots$ , $A\_N$ 이 주어집니다. 이때, 다음 쿼리를 수행하는 프로그램을 작성해 주세요.

$1$ $x$ $y$ : 수열에서 $x$ 인 값을 모두 선택하여, $y$ 로 바꿉니다.
$2$ $z$ : $A\_z$ 를 출력합니다.

입력

첫째 줄에 수열의 크기 $N$ 이 주어집니다. ( $1 \leq N \leq 300\\,000$ )

둘째 줄에는 정수 $A\_1$ , $A\_2$ , $\dots$ , $A\_N$ 이 주어집니다. ( $1 \leq A\_i \leq 300\\,000$ )

셋째 줄에는 쿼리의 개수 $M$ 이 주어집니다. ( $1 \leq M \leq 500\\,000$ )

넷째 줄부터 $M$ 개의 줄에는 쿼리가 한 줄에 하나씩 주어집니다. $1$ 번 쿼리의 경우 $1 \leq x, y \leq 300\\,000$ 이고, $2$ 번 쿼리의 경우 $1 \leq z \leq N$ 입니다. $2$ 번 쿼리는 하나 이상 주어집니다. $x$ , $y$ , $z$ 는 모두 정수입니다.

출력

$2$ 번 쿼리가 주어질 때마다 출력합니다.

예제3

예제 1
입력
```
3
1 10000 7
2
2 2
2 3
```
예상 출력
```
10000
7
```
예제 2
입력
```
2
2 3
3
1 3 4
1 2 3
2 2
```
예상 출력
```
4
```

예제 3

입력

예상 출력