# [Platinum V] 버블 소트 #### [문제 링크](https://www.acmicpc.net/problem/1517) ## 문제 설명 <p>N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.</p> <p>버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.</p> ## 입력 <p>첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.</p> ## 출력 <p>첫째 줄에 Swap 횟수를 출력한다</p> ## 풀이 #### 임의의 i번째 값이 A라고 하면 1~i-1에 있는 값 중에 A보다 큰 수의 개수를 구하면 됩니다. 합병 정렬을 하면서 개수를 구해도 되고, 세그먼트 트리를 사용하여 구해도 됩니다. #### 합볍 정렬을 사용하는 경우 정렬을 해주면서, 자신의 앞에 위치한 자신보다 큰 원소의 개수를 전부 더해주면 됩니다. #### 세그먼트 트리를 사용하는 경우 <정수, 인덱스>를 기준으로 내림차순으로 정렬하여 큰 값부터 넣으면서 넣는 값보다 인덱스가 앞에 있는 수의 개수를 세면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; const int MAX = 1'500'000; int _size=1, arr[MAX]; void update(int idx) { int nodeNum = _size/2+idx; arr[nodeNum]=1; while(nodeNum>1) { nodeNum>>=1; arr[nodeNum] = arr[nodeNum*2] + arr[nodeNum*2+1]; } } long long search(int L, int R, int nodeNum, int nodeL, int nodeR) { if(R<nodeL || nodeR<L) return 0; if(L<=nodeL && nodeR<=R) return arr[nodeNum]; int mid = (nodeL+nodeR)/2; return search(L, R, nodeNum*2, nodeL, mid) + search(L, R, nodeNum*2+1, mid+1, nodeR); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<pair<int, int>> v(n); for(int i=0;i<n;i++) { cin >> v[i].first; v[i].second=i; } sort(v.begin(), v.end(), greater<pair<int, int>>()); while(_size<n) _size<<=1; _size<<=1; long long cnt=0; for(int i=0;i<n;i++) { cnt += search(0, v[i].second-1, 1, 0, _size/2-1); update(v[i].second); } cout << cnt; } ```