[2517] 달리기

https://www.acmicpc.net/problem/2517

2517번: 달리기

<문제>

N에 비해 평소 실력의 범위가 매우 크다. 다만 필요한건 항상 대소관계 뿐이므로, 최대 50만으로 압축해줄 수 있다.

세그먼트 트리를 이용하여 알고싶은건 나보다 평소실력이 낮은 사람의 수이다.

자료구조를 만들고 쿼리의 리턴을 현재 등수(i)에서 빼주면 최고등수가 나온다. 

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> a;
vector<int> segTree;
int n;
bool cmp1(pair<int, int> a, pair<int, int> b) { return a.second < b.second; }
bool cmp2(pair<int, int> a, pair<int, int> b) { return a.first < b.first; }
int query(int i, int s, int e, int l, int r) {
    if (s > r || e < l) return 0;
    if (l <= s && e <= r) return segTree[i];
    int mid = (s + e) / 2;
    return query(2 * i, s, mid, l, r) + query(2 * i + 1, mid + 1, e, l, r);
}
void updateSegTree(int i, int s, int e, int idx) {
    if (s > idx || e < idx) return;
    segTree[i]++;
    if (s == e) return;
    int mid = (s + e) / 2;
    updateSegTree(2 * i, s, mid, idx);
    updateSegTree(2 * i + 1, mid + 1, e, idx);
}
int main(void) {
    int i;
    cin >> n;
    a.resize(n);
    for (i = 0; i < n; i++) {
        int x;
        cin >> x;
        a[i] = {i, x};
    }
    sort(a.begin(), a.end(), cmp1);
    for (i = 0; i < n; i++) {
        a[i].second = i;
    }
    sort(a.begin(), a.end(), cmp2);
    segTree.resize(4 * n);
    for (i = 0; i < n; i++) {
        int ans = query(1, 0, n - 1, 0, a[i].second);
        cout << i - ans + 1 << '\n';
        updateSegTree(1, 0, n - 1, a[i].second);
    }
    return 0;
}