【題解】ZeroJudge d794: 世界排名

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m, b[100005];
vector <long long> v, d;

int getID(long long num){
    //離散化
    return lower_bound(d.begin(), d.end(), num) - d.begin() + 1;
}

int query(int x){
    int ret = 0;
    while (x){
        ret += b[x];
        x -= x & (-x);
    }
    return ret;
}

void update(int x, int y){
    while (x <= n){
        b[x] += y;
        x += x & (-x);
    }
}

int main() {
    while (cin >> n){
        memset(b, 0, sizeof(b));
        v.clear();
        for (int i = 0; i < n; i++){
            cin >> m;
            v.push_back(m);
        }
        d = v;
        sort(d.begin(), d.end());
        for (int i = 1; i <= n; i++){
            int idx = getID(v[i-1]);
            update(idx, 1);
            cout << i - query(idx) + 1 << "\n";
        }
    }
}