Boj 1517) 버블 소트

문제

백준 1517

설명

버블 소트 특성상 문제의 답은 다음과 같은 규칙을 따름

• 어떤 숫자가 있을 때 그 뒤에 오면서 작은 숫자의 갯수의 합
• 이는 Inversion Counting 이라는 잘 알려진 문제임
• 또 다른 문제

해결 방법은 Merge Sort 랑 SegmentTree 가 있음

• 아래 방법은 Fenwick Tree (Segment Tree) 를 이용함

펜윅 트리를 이용한 풀이

Segment Tree 에는 2가지 축이 존재함

1. Nodes 들의 인덱스에 따른 순서
2. 여러 값들이 트리의 값을 업데이트하는 순서

Inversion Count 는 들어오는 순서 와 값의 크기 으로 값이 정해짐

• 이 두 기준을 Segment Tree 에 그대로 적용하면 됨.
  1. 크기를 Node 에 저장하고 순서 에 따라 트리를 갱신해도 되고
  2. 순서를 Node 에 저장하고 크기 에 따라 트리를 갱신해도 됨.
• 여기서는 주어진 숫자의 범위가 커서 순서 를 저장해야함
  • 대신 Input 은 들어오는 순서는 있지만 크기로 정렬된게 아니라 Sort 과정이 별도로 필요함

시간 복잡도

O(nLogn)

코드

template<typename T, size_t _SIZE>
struct BIT
{
	void Update(int i, const T& v) {
		while (i < _SIZE) {
			nodes[i] += v;
			i += (i & -i);
		}
	}

	T Query(int i) {
	    T ans = 0;
	    while (i > 0) {
	        ans += nodes[i];
	        i -= (i & -i);
	    }
	    return ans;
	}
	
	T nodes[_SIZE+1];
};

BIT<long long, 500002> fw;
pair<int, int> inputs[500002];


int main()
{
    fastio;
    int n;
    cin >> n;

    int tmp;
    for (int i = 1; i <= n; i++)
    {
        cin >> tmp;
        inputs[i] = { tmp, i };
    }
    sort(inputs + 1, inputs + n + 1);
    
    long long cnt = 0;
    for (int i = n; i >= 1; i--) {
        cnt += fw.Query(inputs[i].second);
        fw.Update(inputs[i].second, 1);
    }
    cout << cnt;
}