1265. 数星星（树状数组/蓝桥杯）

题目：

输入样例：

5
1 1
5 1
7 1
3 3
5 5

输出样例：

1
2
1
1
0

思路：?树状数组

?

?代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=32010;
int n;
int tr[N],level[N];

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

//在位置x上+1,不是把x+1
void add(int x,int v)//因为tr[]没有初始化，所以x位置刚开始为0
{
    for(int i=x;i<=N;i+=lowbit(i))tr[i]+=v;
}

//横坐标在1~x之间星星数量的在线（动态）前缀和
int query(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i))res+=tr[i];
    return res;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        x++;//树状数组下标必须从1开始，故横坐标整体+1
        level[query(x)]++;//在线前缀和作为级数下标
        add(x,1);//
    }
    for(int i=0;i<n;i++)printf("%d\n",level[i]);
    return 0;
}