문제
러스티의 도넛🍩 가게에는 $1$번부터 $N$번까지의 도넛 반죽 기계 $N$개가 있다. 각 도넛 반죽 기계에는 도넛 반죽이 하나씩 들어 있다. 각 도넛 반죽은 여러 가지 맛을 가질 수 있는데, 맛은 $1$ 이상 $10^9$ 이하의 정수로 표현할 수 있다. 서로 다른 두 도넛 반죽은 합칠 수 있다. 합쳐진 반죽이 가진 맛의 집합은 두 반죽이 가진 맛의 합집합이다. 여러분은 처음 도넛 반죽이 가진 맛의 범위가 주어질 때 러스티의 반죽 과정에 따라 아래 명령을 $Q$번 수행해야 한다.
1 a b: $a$번 기계에 든 반죽과 $b$번 기계에 든 반죽을 남김없이 싹싹 긁은 후 모두 합쳐 $a$번 기계에 넣는다.2 a: $a$번 기계에 든 반죽이 가진 맛의 개수를 출력한다.
입력
첫째 줄에 도넛 반죽 기계의 수 $N$와 명령의 수 $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 200\,000)$
다음 $N$개 줄에 걸쳐 도넛 반죽 기계에 든 도넛 반죽의 맛의 범위가 주어진다. 그중 $i$번째 줄에는 정수 $\ell_i$, $r_i$가 공백으로 구분되어 주어진다. 이는 $i$번 도넛 반죽 기계에 든 반죽의 맛에 $\ell_i$ 이상 $r_i$ 이하의 모든 정수가 포함된다는 뜻이다. $(1 \le \ell_i \le r_i \le 10^9)$
다음 $Q$개 줄에 걸쳐 명령이 주어진다. 각 명령은 아래 형식 중 하나로 주어진다.
1 a b: $a$번 기계에 든 반죽과 $b$번 기계에 든 반죽을 남김없이 싹싹 긁은 후 모두 합쳐 $a$번 기계에 넣는다. $a$번 기계와 $b$번 기계에 반죽이 남아 있는 경우만 주어진다. $(1 \le a, b \le N;$ $a \ne b)$2 a: $a$번 기계에 든 반죽이 가진 맛의 개수를 출력한다. $a$번 기계에 반죽이 남아 있는 경우만 주어진다. $(1 \le a \le N)$
2번 명령은 하나 이상 주어진다.
출력
2번 명령이 주어질 때마다 $a$번 기계에 든 반죽이 가진 맛의 수를 한 줄에 출력한다.
예제 입력 1
3 7 1 3 2 4 6 8 2 1 2 2 2 3 1 1 3 2 1 1 2 1 2 2
예제 출력 1
3 3 3 6 7
처음에 $1$번 기계에는 $\{1, 2, 3\}$, $2$번 기계에는 $\{2, 3, 4\}$, $3$번 기계에는 $\{6, 7, 8\}$의 맛을 가진 반죽이 들어 있다.
네 번째 명령에서 $1$번과 $3$번 기계에 든 반죽을 합친 뒤, $1$번 기계에는 $\{1, 2, 3, 6, 7, 8\}$의 맛을 가진 반죽이 들어 있다.
여섯 번째 명령에서 $2$번과 $1$번 기계에 든 반죽을 합친 뒤, $2$번 기계에는 $\{1, 2, 3, 4, 6, 7, 8\}$의 맛을 가진 반죽이 들어 있다.
출처
Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2024. 07. C번
- 문제를 만든 사람: kiwiyou
- 문제를 검수한 사람: bnb2011, djs100201, heeda0528, lky7674, snrnsidy, utilforever