자녀 줄세우기

출처 제5회 랴오차오컵 지역 C++ B그룹

알고리즘 트리 배열 그리디 병합 정렬

문제 설명

n명의 아이들이 일렬로 서 있습니다.

이제 키가 작은 순서대로 정렬해야 하지만, 인접한 두 아이만 교체할 수 있습니다.

각 아이에는 불만도가 있습니다.

처음에는 모든 아이들의 불만도가 0입니다.

어떤 아이가 처음 교체를 요청받으면 불만도가 1 증가하고, 두 번째 교체를 요청받으면 불만도가 2 증가합니다(즉, 불만도는 3이 됩니다). 이런 식으로 k번째 교체를 요청받을 때마다 불만도가 k만큼 증가합니다.

모든 아이들을 키 순으로 정렬하기 위해 필요한 불만도의 합의 최솟값은 얼마입니까?

키가 같은 아이들이 있다면, 서로의 순서는 상관없습니다.

입력 형식

첫 번째 줄에는 아이들의 수를 나타내는 정수 n이 포함됩니다.

두 번째 줄에는 각 아이의 키를 나타내는 n개의 정수 H1, H2, ..., Hn이 포함됩니다.

출력 형식

한 줄에 아이들의 불만도 합의 최솟값을 나타내는 정수를 출력합니다.

데이터 범위

1≤n≤100000,
0≤Hi≤1000000

입력 예시:

3
3 2 1

출력 예시:

9

예시 설명

먼저 키가 3과 2인 아이들을 교체한 다음, 키가 3과 1인 아이들을 교체하고, 마지막으로 키가 2와 1인 아이들을 교체합니다. 각 아이의 불만도는 3이므로 총합은 9입니다.

해결 방법

직접적으로 n^2 접근은 데이터가 너무 커서 비효율적입니다. 대신, 각 숫자의 교체 횟수는 이 숫자보다 큰 숫자의 개수와 작은 숫자의 개수의 합과 같다는 것을 이해할 수 있습니다. 또한, '어떤 아이가 k번째 교체를 요청받을 때마다 불만도가 k만큼 증가한다'는 점을 고려하면 n*(n-1)/2 공식을 사용하여 계산할 수 있습니다. 그런 다음 모든 아이들의 불만도 값을 누적하면 됩니다.

C++ 코드

#include<iostream>
#include<cstring>

using namespace std;
typedef long long LL;
const int MAX = 1e6 + 10;
int heights[MAX], counts[MAX], fenwick[MAX]; // 키, 개수, 펜윅 트리
int n;

int lowbit(int x) { return x & -x; }
void update(int x) {
    for(int i = x; i < MAX; i += lowbit(i)) 
        fenwick[i]++;
}
int query(int x) {
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) 
        res += fenwick[i];
    return res;
}
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> heights[i];
        heights[i]++; // 펜윅 트리는 1부터 시작해야 함
        
        counts[i] = query(MAX - 1) - query(heights[i]); // i보다 큰 수
        update(heights[i]);
    }
    
    memset(fenwick, 0, sizeof fenwick); // 펜윅 트리 초기화
    
    for(int i = n - 1; i >= 0; i--) {
        counts[i] += query(heights[i] - 1); // i보다 작은 수
        update(heights[i]);
    }
    
    LL result = 0;
    for(int i = 0; i < n; i++) 
        result += (LL)counts[i] * (counts[i] + 1) / 2; // 공식 계산 및 누적
        
    cout << result;
    
    return 0;
}