[백준 18874] Haircut

문제

www.acmicpc.net/problem/18874

 

알고리즘

segment tree

 

풀이

$j$보다 긴 머리카락들이 $j$가 될 때, badhair의 수를 구하는 문제입니다.

 

관찰이 조금 필요한 문제입니다. 우선 머리카락 길이가 변하는 것을 생각하지 않고 counting inversion을 할 때 브루트포스로 하면 $N^2$이 필요하고 문제에서 $N$제한은 10만이므로 $NlogN$에 inversion을 셀 수 있는 세그먼트 트리를 이용해야합니다. 

 

쿼리($j$)마다 머리카락 길이를 업데이트를 하려면 아무리 빨리한다 하더라도 $O(N)$보다 빠를 순 없고 inversion을 세면 결국 시간초과입니다.

 

문제의 핵심은 $j$보다 긴 머리카락들이 $j$가 될 때, badhair을 발생시키는 머리카락들은 각자의 길이가 $j$미만이면서 각자의 위치 왼쪽에 있는 머리카락들보다 짧은 머리카락입니다.

 

즉 머리카락의 길이마다(각자의 길이가 $j$미만) inversion(각자의 위치 왼쪽)을 세주면 정답을 구할 수 있습니다.

 

코드

    #include <bits/stdc++.h>
    #define rep(i, n) for (int i = 0; i < n; ++i)
    #define REP(i, n) for (int i = 1; i <= n; ++i)
    using namespace std;

    const int MAXN = 1e5 + 5;
    #define int long long

    int N;
    int ans[MAXN], BIT[MAXN], psum;

    void update(int idx, int val) {
        ++idx;
        while (idx <= MAXN) {
            BIT[idx] += val;
            idx += idx & -idx;
        }
    }

    int query(int idx) {
        ++idx;
        int ret = 0;
        while (idx > 0) {
            ret += BIT[idx];
            idx -= idx & -idx;
        }
        return ret;
    }

    signed main() {
    #ifndef ONLINE_JUDGE
        freopen("in", "r", stdin);
        freopen("out", "w", stdout);
    #endif
        cin.tie(NULL);
        cout.tie(NULL);
        ios::sync_with_stdio(false);

        cin >> N;
        rep(i, N) {
            int v;
            cin >> v;
            ans[v] += i - query(v);
            update(v, 1);
        }
        rep(i, N) {
            cout << psum << '\n';
            psum += ans[i];
        }

        return 0;
    }