BOJ 4157 : Frosh Week

• 문제 링크 : boj.kr/4157
• 난이도 : P5
• 태그 : 세그먼트 트리, 정렬

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

template<typename T> struct segTree {
	int n;
	T id;
	vector<T> t;
	T(*merge)(T, T);
	segTree(int N, T ID, T(*_merge)(T, T)): n(N), id(ID), merge(_merge) { t.resize(N<<1, id); }					
	void update(int p, T val) {
		for (t[p+=n] = val; p > 1; p >>= 1) {
			if(p&1) t[p>>1] = merge(t[p^1], t[p]);
			else t[p>>1] = merge(t[p], t[p^1]);
		}
	}
	T query(int l, int r) {//query on interval [l, r)
		T lret=id, rret=id;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l&1) lret = merge(lret, t[l++]);
			if(r&1) rret = merge(t[--r], rret);
		}
		return merge(lret, rret);
	}
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<int> arr(n);
    for(auto &u : arr) cin >> u;
    unordered_map<int, int> _m;
    for(int i = 0; i < n; i++) {
        _m[arr[i]] = i+1;
    }
    sort(all(arr));

    segTree<int> s(n+1, 0, [](int a, int b){return a + b;});
    ll ans = 0;
    for(int i = 0; i < n; i++) {
        ans += s.query(_m[arr[i]], n+1);
        s.update(_m[arr[i]], 1);
    }
    cout << ans;

    return 0;
}

---

풀이

#7578과 같은 문제이다.

하지만 재귀 기반 세그먼트 트리를 사용하면 시간초과를 받는다.