BOJ 3006 터보소트

15:03
세그먼트 트리에 터보소트를 적용시키지 않은 값의 개수을 저장한다.
v[i] = x라 할때 x를 앞으로 움직이려면 tree[1~i]-1 의 값만큼 움직여야 하고
x를 뒤로 움직이려면 tree[i~n]-1 의 값만큼 움직여야 한다.
움직이고 나면 i번째 값은 트리에서 0으로 바꿔준다.

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>

#define INF 987654321
#define INF2 2147483647
#define f first
#define s second
#define x first
#define y second
#define all(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ti3 = tuple<int, int, int>;

class segment {
public:
    vector<ll> tree; //tree[node] := a[start ~ end] 의 합

    segment() {}
    segment(int size) {
        this->resize(size);
    }
    void resize(int size) {
        size = (int) floor(log2(size)) + 2;
        size = pow(2, size);
        tree.resize(size);
    }
    ll init(int node, int start, int end) {
        if(start == end) return tree[node] = 1;
        else return tree[node] = init(2 * node, start, (start + end) / 2) +
                                 init(2 * node + 1, (start + end) / 2 + 1, end);
    }
    ll sum(int node, int start, int end, int left, int right) {
        if(right < start || end < left) return 0;
        if(left <= start && end <= right) return tree[node];
        return sum(node * 2, start, (start + end) / 2, left, right) +
               sum(node * 2 + 1, (start + end) / 2 + 1, end, left, right);
    }
    void update(int node, int start, int end, int index, ll diff) {
        if(index < start || end < index) return;
        tree[node] += diff;
        if(start != end) {
            update(node * 2, start, (start + end) / 2, index, diff);
            update(node * 2 + 1, (start + end) / 2 + 1, end, index, diff);
        }
    }
};

int N;
vector<int> v;
unordered_map<int,int> Idx;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N;
    v.resize(N+1);
    for(int i=1; i<=N; i++) {
        cin >> v[i];
        Idx[v[i]] = i;
    }
    segment root(N);
    root.init(1,1,N);
    for(int left = 1, right = N; left <= right; left++, right--) {
        root.update(1,1,N,Idx[left],-1);
        cout << root.sum(1,1,N,1,Idx[left]) << '\n';
        if(left == right) break;
        root.update(1,1,N,Idx[right],-1);
        cout << root.sum(1,1,N,Idx[right],N) << '\n';
    }

    return 0;
}