AcWing 1265. 数星星
原题链接
中等
作者:
史一帆
,
2022-01-07 10:48:39
,
所有人可见
,
阅读 256
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 32010;
int c[N], ans[N];
int n;
int x, y;
int lowbit(int x)
{
return x & -x;
}
int sum(int i)
{
int res = 0;
for (; i > 0; i -= lowbit(i))
res += c[i];
return res;
}
void add(int i, int z)
{
for (; i < N; i += lowbit(i))
c[i] += z;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> x >> y;
x ++ ;
ans[sum(x)] ++ ;
add(x, 1);
}
for (int i = 0; i < n; i ++ )
cout << ans[i] << endl;
return 0;
}