【題目敘述】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";
}
}
}