1265. 数星星(树状数组/蓝桥杯)

2023-12-17 20:33:12

题目:

输入样例:
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;
}

文章来源:https://blog.csdn.net/asdfghrfh/article/details/135047649
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。