AcWing 1265. 数星星
原题链接
中等
作者:
海里长蘑菇
,
2024-04-10 17:31:24
,
所有人可见
,
阅读 1
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 32020;
int n;
int tr[N],level[N];
int lowbit(int x)
{
return x & (-x);
}
void add(int x)
{
for(int i = x ; i < N ; i+=lowbit(i)) tr[i]++; //这里取值N是为了防止越界问题, i< 32001就好了,这里N更大,所以干脆就直接用了
}
int query(int x)
{
int ans = 0 ;
for(int i = x ; i > 0 ; i -= lowbit(i)) ans += tr[i];
return ans;
}
int main()
{
scanf("%d", &n);
int m = n;
while(n--)
{
int x,y;
scanf("%d%d" , &x , &y);
x++; //保证下标从1 开始;
level[query(x)]++; //加进去之前 统计数字
add(x); //避免 树状数组左闭右开的区间性质;
}
for( int i = 0 ; i < m ; i ++ ) printf("%d\n" , level[i]);
return 0 ;
}
/*
震惊
for循环与 while循环的大不同
while循环竟然会改变变量的值。
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 32020;
int n;
int tr[N],level[N];
int lowbit(int x)
{
return x & (-x);
}
void add(int x)
{
for(int i = x ; i < N ; i+=lowbit(i)) tr[i]++; //这里取值N是为了防止越界问题, i< 32001就好了,这里N更大,所以干脆就直接用了
}
int query(int x)
{
int ans = 0 ;
for(int i = x ; i > 0 ; i -= lowbit(i)) ans += tr[i];
return ans;
}
int main()
{
scanf("%d", &n);
for(int i = 0 ; i < n ; i++)
{
int x,y;
scanf("%d%d" , &x , &y);
x++; //保证下标从1 开始;
level[query(x)]++; //加进去之前 统计数字
add(x); //避免 树状数组左闭右开的区间性质;
}
for( int i = 0 ; i < n ; i ++ ) printf("%d\n" , level[i]);
return 0 ;
}