문제
나도리는 자신을 터트린 나도리팡의 제작자에게 복수하기 위해 만반의 준비를 해왔다. 각 나도리 $i$는 크기 $s_i$를 가지며, 정확히 하나의 나도리 그룹에 속한다. 두 나도리 그룹이 융합하면 둘에 속한 모든 나도리로만 이루어진 새 나도리 그룹 하나로 대체된다. 나도리 그룹의 전투력은 그룹에 속한 서로 다른 두 나도리의 크기를 곱한 것을 모두 합한 값이다.
아래는 나도리 그룹 $G$의 전투력을 수식으로 표현한 것이다.
$$\sum_{i, j\in G,\ i < j}s_i\cdot s_j$$
나도리들의 복수를 도와주기 위하여 다음과 같은 쿼리를 수행하는 프로그램을 작성해보자.
- $a \, b$ : 나도리 $a$가 속한 나도리 그룹과 나도리 $b$가 속한 나도리 그룹을 융합한 뒤, 나도리 $a$와 나도리 $b$가 속한 나도리 그룹의 전투력을 출력한다. (단, 같은 나도리 그룹끼리는 융합하여도 변화가 없다)
입력
첫째 줄에 나도리의 수 $N (2 \leq N \leq 200\,000)$, 쿼리의 수 $Q (1 \leq Q \leq 200\,000)$가 공백으로 구분되어 주어진다.
둘째 줄에 각 나도리의 크기를 나타내는 $N$개의 정수 $s_1, s_2, \dots, s_N$이 공백으로 구분되어 주어진다. $(0 \leq s_i \leq 2\,000)$
셋째 줄부터 $Q$개 줄에 걸쳐 쿼리를 나타내는 정수 $a, b$가 공백으로 구분되어 주어진다. $(1 \leq a, b \leq N; a \neq b)$
출력
$Q$개의 줄에 걸쳐 쿼리의 결괏값을 출력한다.
예제 입력 1
3 3 2 3 4 1 2 2 3 1 3
예제 출력 1
6 26 26
첫 번째 쿼리에서 나도리 $1$가 속한 나도리 그룹과 나도리 $2$가 속한 나도리 그룹이 융합되어 $2 \cdot 3 = 6$의 전투력을 갖는 나도리 그룹이 만들어졌다.
두 번째 쿼리에서 나도리 $1$과 나도리 $2$가 속한 나도리 그룹과 나도리 $3$의 나도리 그룹이 융합되어 $2 \cdot 3 + 2 \cdot 4 + 3 \cdot 4 = 26$의 전투력을 갖는 나도리 그룹이 만들어졌다.
세 번째 쿼리에서 나도리 $1$과 나도리 $3$은 이미 $26$의 전투력을 가진 나도리 그룹에 같이 속해있다.
출처
Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2023. 06. B번
- 문제를 만든 사람: swoon
- 문제를 검수한 사람: chogahui05, djs100201, dohoon, dong_gas, heeda0528, ljwljw8541, pjshwa, rustiebeats, snrnsidy, tony9402, utilforever