【題解】ZeroJudge d794: 世界排名

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d794
【解題想法】數值離散化 + BIT 樹狀數組【筆記

  • 【技巧】如需去重 (移除重複的值),
    • d.erase(unique(d.begin(), d.end()), d.end());
#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";
        }
    }
}
分享本文 Share with friends