AcWing 1265. 数星星
原题链接
中等
作者:
叙利亚悍匪_0
,
2024-03-21 10:21:19
,
所有人可见
,
阅读 2
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 32010;
int n;
int tr[N],ans[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x)
{
for(int i = x;i<=N;i += lowbit(i)) tr[i]++;
}
int query(int x)
{
int res = 0;
for(int i = x;i>0;i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
cin>>n;
for(int i = 0;i<n;i++)
{
int x,y;
cin>>x>>y;
x++;
//cout<<query(x)<<endl;
ans[query(x)]++;
add(x);
}
for(int i = 0;i<n;i++)
{
cout<<ans[i]<<endl;
}
}