[BOJ 3006] 터보소트

문제 출처 : https://www.acmicpc.net/problem/3006

 

풀이 :

 

세그먼트 트리 문제입니다.

각 숫자가 자신의 자리를 찾아가는데 항상 작은 숫자는 왼쪽 큰 숫자는 오른쪽으로 가기 때문에 홀수번째 일때는 왼쪽숫자의 갯수, 짝수번째는 오른쪽 숫자의 갯수로 옮기는 횟수를 쉽게 구할 수 있습니다.

각 숫자의 위치를 따로 저장해주고 세그먼트 트리에 각 숫자의 위치의 값을 1로 채웁니다.

그다음 세그먼트 트리를 활용하여

1. 홀수번째 : 찾으려는 값의 왼쪽 범위의 구간합

2. 짝수번째 : 찾으려는 값의 오른쪽 범위의 구간합

을 구하시면 됩니다.

구하신 후에는 찾으려는 값의 세그먼트 트리에 저장된 정보를 0으로 바꾸고 업데이트 시키시면 됩니다.

 

#include<iostream>
#include<math.h>
using namespace std;
 
int n, base, seg[1 << 19], c, pos[100001];
 
int search(int idx, int l, int r, int a, int b) {
    if (a > b)return 0;
    if (l > b || r < a)return 0;
    if (a <= l && b >= r)return seg[idx];
    int mid = (l + r + 1) / 2;
    return search(idx * 2, l, mid - 1, a, b) + search(idx * 2 + 1, mid, r, a, b);
}
 
int main()
{
    cin >> n;
    base = pow(2, (int)log2(n) + 1);
    for (int i = 1; i <= n; i++) {
        cin >> c;
        pos[c] = i;
        seg[i + base - 1] = 1;
    }
    for (int i = base - 1; i > 0; i--)seg[i] = seg[i * 2] + seg[i * 2 + 1];
    for (int i = 1; i <= n; i++) {
        if (n % 2 == 0 && n / 2 < i)break;
        cout << search(1, 1, base,1,pos[i] - 1)<<'\n';
        if (n % 2 && n / 2 < i)break;
        int idx = pos[i] + base - 1;
        seg[idx] = 0;
        for (idx /= 2; idx > 0; idx /= 2)seg[idx] = seg[idx * 2] + seg[idx * 2 + 1];
        cout << search(1, 1, base, pos[n - i + 1] + 1, n) << '\n';
        idx = pos[n - i + 1] + base - 1;
        seg[idx] = 0;
        for (idx /= 2; idx > 0; idx /= 2)seg[idx] = seg[idx * 2] + seg[idx * 2 + 1];
    }
}