POJ 2352 Stars[树状数组]

#include <iostream>
using namespace std;

const int N = 4e4;  // 注意此处
int arr[N] = {0};
int ans[N/2] = {0}, n;

int lowbit(int x) {
    return x & (-x);
}

void add(int i, int v) {
    while(i < N) {  // 注意是 N
        arr[i] += v;
        i += lowbit(i);
    }
}

int Sum(int x) {
    int res = 0;
    while(x) {
        res += arr[x];
        x -= lowbit(x);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i = 0; i < n; i++) {
        int x, y; cin>>x>>y;
        ans[Sum(++x)]++;  // x 要加一
        add(x, 1);
    }
    for(int i = 0; i < n; i++)
        cout<<ans[i]<<endl;

    return 0;
}