4-3 Inversion Counting

길이 앤의 수열 에이가 주어짐. 에이의 원소들을 각각 에이, 에이,  에이앤 이라고 할 때 아이<제이 인덱 에이아이가 에이 제이라면 인버젼이라고 함

주어진 순열에서 인버젼의 수를 구하는 프로그램

#include <stdio.h>

#define MAX_N 100001

int N, input[MAX_N], tree[MAX_N];
long long Ans;

// Index Tree - 변하는 배열의 구간 합을 O(logN)에 계산
// 인덱스 트리. 트리가 어떻게 변화하는지 확인 할 것
void Add(int idx, int val)
{
    while (idx <= N)
    {
        tree[idx] += val;
        idx += (idx & -idx);
    }
}

long long Sum(int idx)
{
    long long s = 0;
    while (idx > 0)
    {
        s += tree[idx];
        idx -= (idx & -idx);
    }
    return s;
}


int main(void)
{
    freopen("test.txt", "r", stdin);
    int T, tc, i, idx;
    long long tmp;
    setbuf(stdout, NULL);
    scanf("%d\n", &T);
    for (tc = 1; tc <= T; tc++)
    {
        scanf("%d\n", &N); // 길이를 받음

        for (i = 1; i <= N; i++)
        {
            scanf("%d", &input[i]); // 수열을 받음
            tree[i] = 0;
        }
        scanf("\n");

        Ans = 0;
        Add(input[1], 1);
        for (i = 2; i <= N; i++)
        {
            idx = input[i];
            tmp = (i - 1) - Sum(idx);
            Ans += tmp;
            Add(idx, 1);
            //printf("%d(%lld) ", idx, tmp);
        }
        printf("#%d %lld\n", tc, Ans);
    }

    return 0;
}

- 왜 이렇게 풀이
- 트리와 링크드 리스크 만들었을 때 장점
- 그리고 비트 연산 했을 때 장점
- 오케이 접수