AcWing 1265. 数星星
原题链接
中等
作者:
Bear_King
,
2021-01-19 11:01:30
,
所有人可见
,
阅读 306
数星星
创建一个树状数组存储的是当前得前面有多少个星星,用level数组存储每一行得星星数目
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 32010;
int n;
int tr[N] , level[N];//level每个横坐标下有多少个星星
int lowbit(int x)
{
return x & -x;
}
void add(int x)
{
for(int i = x;i <= N;i += lowbit(i)) tr[i] ++;
}
int sum(int x)
{
int res = 0;
for(int i = x;i;i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
scanf("%d",&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 ++) printf("%d\n",level[i]);
}