数星星 刷题笔记 （树状数组）

依题意  

要求每个点  x, y 的左下方有多少个星星  

又因为  是按照y从小到大 给出的

所以 我们在计算个数的时候是按照y一层层变大来遍历的

因此我们在处理每一个点的时候 

只需要看一下 

当前的点有多少个点的x值比当前点小即可

树状数组的 操作模板

P3374 【模板】树状数组 动态求连续区间和 刷题笔记-CSDN博客

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=32010;
int a[N],s[N],level[N];
int lowbit(int x){
    return x&-x;
}

void change(int x){
    for (int i = x; i < N; i += lowbit(i)) s[i] ++ ;
}

int query(int k){
    int res=0;
    while(k){
        res+=s[k];
        k-=lowbit(k);
    }
    return res;
    
}
int n;
int main(){
    
    cin>>n;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        x++;
        level[query(x)]++;
        change(x);
        
    }
    
    for (int i = 0; i < n; i ++ ) printf("%d\n", level[i]);

    return 0;
}