AcWing
1265. 数星星
树状数组：
树状数组(二叉索引树)–Binary_Indexed_Tree
维护树状数组tr[N]，用来表示某个x坐标下对应的点数。由于题目按y坐标递增、x坐标递增的顺序给出坐标，只需要在读取数据时动态维护树状数组tr[N]，与层数对应星星数的数组lev[N]即可。注意树状数组的下标从1开始，而题目给出的x坐标从0开始，所以将所有的x坐标+1.
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 32010;
int tr[N], lev[N];
int lowbit(int x){return x & -x;}
void add(int x, int v){
for(int i = x; i <= N - 1; i += lowbit(i)) tr[i] += v;
}
int query(int x){
int sum = 0;
for(int i = x; i >= 1; i -= lowbit(i)) sum += tr[i];
return sum;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
int x, y;
cin >> x >> y;
x++;
lev[query(x)] ++;
add(x, 1);
}
for(int i = 0; i <= n - 1; i++) cout << lev[i] << "\n";
return 0;
}