AcWing 1265. 数星星
原题链接
中等
作者:
liebe_1
,
2024-03-30 18:58:43
,
所有人可见
,
阅读 12
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 15010, M = 32010;
int n;//星星数量
int x,y;//星星坐标
int ans[N];//存储每个星级的星星数量
int t[M];//树状数组
int lowbit(int x) {
return x&-x;
}
//单点修改
void add(int x) {
for(int i = x; i < M; i += lowbit(i))t[i] += 1;
}
//区间查询
int ask(int x) {
int res = 0;
for(int i = x; i ; i -= lowbit(i))res += t[i];
return res;
}//计算出星星的级数
//每输入一个星星,就计算在这个星星之前的有着更小x的星星数量
int main() {
scanf("%d",&n);
for(int i = 0; i < n; i++) {
scanf("%d%d",&x,&y);
x++;
int t = ask(x);
ans[t]++;
add(x);
}
for(int i = 0; i < n; i++)printf("%d\n",ans[i]);
return 0;
}