acwing1265. 数星星

题目

天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。

如果一个星星的左下方（包含正左和正下）有 k 颗星星，就说这颗星星是 k 级的。

题解

#include<iostream>
using namespace std;
const int N=32010;
int n,level[N],tree[N];
int lowbit(int x){
    return x&(-x);
}
void add(int x){
    for(int i=x;i<N;i+=lowbit(i))
        tree[i]++;
    
}
int sum(int x){
    int ans=0;
    for(int i=x;i;i-=lowbit(i))ans+=tree[i];
    return ans;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        x++;
        level[sum(x)]++;
        add(x);
    }
    for(int i=0;i<n;i++)cout<<level[i]<<endl;
    
    return 0;
}