10888 - 두 섬간의 이동

https://www.acmicpc.net/problem/10888

다리를 N-1개 지을때마다 그 때까지의 정부가 원하는 2개의 값 현황을 알려줘야한다. 정부가 원하는 값 2개는

• 두 섬 간에 왕래가 가능한 섬들 (i,j) (i<j) 쌍들의 개수
• 두 섬 (i,j)가 왕래 가능할 때 섬 i에서 섬 j까지 가기 위해 이용해야 하는 최소 다리 개수의 합

와 같다. 원하는 값을 설명하기 너무 기니까 왕래 가능한 쌍들의 개수를 pairs, 섬 들이 서로 이동하는데 필요한 최소 다리 개수의 합을 bridges라고 하겠다.

이 문제 역시 서로소 집합(Disjoint Set)으로 해결할 수 있다. pairs는 서로 연결된 섬들의 개수를 통해 알 수 있다.
서로 연결된 섬들의 개수를 $x$라 하면 $x=4$일 때 (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) 로 6개이다.
i번째에서 i<j인 개수만큼 더하므로 $$ pairs = \sum_{k=1}^x k$$ 로 나타낼 수 있다.

그럼 bridges는 이러한 pairs개 만큼의 쌍들이 x-1개, x-2개, ..., 1개만큼 떨어져있으므로 전부 더한 값이다.
예를 들어 자세히 설명하자면, 섬 4개에 번호를 붙여서 1-2-3-4 라 하면, 1에서 나올 수 있는 쌍은 ~2, ~3, ~4까지이고 각각 최소 다리의 개수는 1, 2, 3 이므로 1에서 출발하는 경우는 1+2+3=6 이다. 2에서 출발하는 경우는 1+2 이고, 3에서 출발하는 경우는 1 (3-4. 1개)이다. 그럼 섬이 4개일 때 bridges는 1+(1+2)+(1+2+3)=10 이다.

수식으로는 $$\sum_{k=1}^{n-1} \left(\sum_{i=1}^k i\right) = \frac{(n-1)n(n+1)}{6}$$ 가 된다.

그리고 갈라져있던 두 집합이 합쳐지는 경우가 있는데, 이 때는 각 집합에서의 pairs와 bridges를 빼고 합친 후의 pairs와 bridges를 더해주면 전체 값은 유지되면서 갱신한 후에 센 값과 같다.

다음은 코딩할 때 사용한 샘플 입출력이다.

예제 입력

5
1 2 4 3

예제 출력

1 1
3 4
4 5
10 20

소스

#include <cstdio>

typedef long long lld;

int r[100001];
lld C[100001];

int find(int n){
    if(n == r[n]) return n;
    return r[n] = find(r[n]);
}

int merge(int p, int q){
    p = find(p);
    q = find(q);
    if(p != q){
        r[q] = p;
        C[p] += C[q];
        C[q] = 1;
    }
    return C[p];
}

lld sum3(int n){
    return n*(n-1LL)*(n+1)/6LL;
}

int main(){
    int i, n, k;
    lld S[100001]={0};
    lld pairs = 0, bridges = 0;
    scanf("%d", &n);
    for(i=1; i<=n; ++i){
        r[i] = i, C[i] = 1;
        S[i] = S[i-1] + i;
    }
    for(i=1; i<n; ++i){
        scanf("%d", &k);
        int k0 = find(k), k1 = find(k+1);
        pairs -= S[C[k0]] + S[C[k1]];
        bridges -= sum3(C[k0]) + sum3(C[k1]);
        bridges += sum3(merge(k0, k1));
        pairs += S[C[k0]] * S[C[k1]];
        printf("%lld %lld\n", pairs, bridges);
    }
    return 0;
}