解题思路:树状数组
注意事项:
参考代码:
#include<bits/stdc++.h>
using namespace std;
const int N=15005,M=32005;
int a[N],b[M],n;
int lowbit(int i){return (-i)&i;}
void add(int i,int z)
{
for(;i<=M;i+=lowbit(i))
b[i]+=z;
}
int sum(int i)
{
int s=0;
for(;i>0;i-=lowbit(i))
s+=b[i];
return s;
}
int main()
{
int x,y;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x>>y;//y其实作用不大
x++;//确保x>0,因为树状数组是从一开始
a[sum(x)]++;//因为y是升序,只要算前面横坐标小于等于当前x的星星的数目就可以知道级数(并且星星是没有重叠的),就是sum(x)
add(x,1);//add放后面防止把当前的星星加上
}
for(int i=0;i<n;i++)
cout<<a[i]<<endl;
return 0;
}
0.0分
2 人评分