용사 길드 합병
골드 IV의견: 0
용사들의 나라에 \(N\)명의 용사가 있다. 각 용사 \(i\)의 전투력은 \(p_i\)이며, 처음에 각 용사는 자기 혼자로 이루어진 길드에 속한다.
다음 두 종류의 명령이 \(Q\)번 주어진다.
- 명령 1 \(u\) \(v\): 용사 \(u\)의 길드와 용사 \(v\)의 길드를 합병한다. (이미 같은 길드라면 아무 변화도 없다.)
- 명령 2 \(u\): 용사 \(u\)가 속한 길드의 최대 전투력과 길드 인원 수를 출력한다.
명령 2가 주어질 때마다 해당 정보를 출력하여라.
- \(1 \le N \le 100\,000\)
- \(1 \le Q \le 200\,000\)
- \(1 \le p_i \le 10^9\)
- \(1 \le u, v \le N\)
첫째 줄에 용사의 수 \(N\)과 명령의 수 \(Q\)가 공백으로 구분되어 주어진다.
둘째 줄에 \(N\)명의 용사의 전투력 \(p_1, p_2, \ldots, p_N\)이 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 명령이 주어진다. 명령 1은 1 u v, 명령 2는 2 u 형태이다.
명령 2가 주어질 때마다 한 줄에 최대 전투력과 길드 인원 수를 공백으로 구분해 출력한다.
5 6
5 3 8 2 7
2 1 0
1 1 2
2 1 0
1 2 3
2 3 0
2 4 0
5 1
5 2
8 3
2 1
처음에 각 용사는 혼자이다. 용사 \(1\)의 길드는 전투력 \(5\), 인원 \(1\)이다. \(1\)과 \(2\)가 합병하면 최대 전투력은 \(5\), 인원은 \(2\)이다. 추가로 \(2\)와 \(3\)이 합병하면 \(\{1,2,3\}\)의 최대 전투력은 \(8\), 인원은 \(3\)이다. 용사 \(4\)의 길드는 여전히 혼자로 전투력 \(2\), 인원 \(1\)이다.
3 3
10 10 10
1 1 2
1 2 3
2 1 0
10 3
\(1{-}2{-}3\)이 모두 합쳐지면 최대 전투력은 \(10\)이고 인원은 \(3\)이다.
riseoj 작성
출처 Original
평가 및 의견
용사 길드 합병
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
용사 길드 합병