声明:本题解提供一种离散化的思路,此题不离散化也能AC!!不喜勿喷
分析
在用树状数组来解答此题目时,会将数组tr[]开到32000,也就是x的范围。而本题的星星却只有N,也就是说,当N<x时,会造成一定程度的浪费,因此将星星的x坐标离散化成1至N,使树状数组开到与N一样大即可。这样也能完美解决x=0导致程序卡死的情况。所用的离散化方法是基于STL进行离散化。
AC代码
//离散化+树状数组
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=15010;
int tr[N]={0};//树状数组
int a[N];//用来存放原始星星的横坐标
int b[N];//用来存放离散化后星星的坐标
int Great[N]={0};
int lowbit(int x)
{
return x&-x;
}
void add(int pos,int d)
{
while(pos<=N)
{
tr[pos]+=d;
pos+=lowbit(pos);
}
}
int sum(int pos)
{
int res=0;
while(pos)
{
res+=tr[pos];
pos-=lowbit(pos);
}
return res;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int y;
scanf("%d%d",&a[i],&y);
b[i]=a[i];
}
//利用STL将离散化后的结果存入b数组
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
b[i]=lower_bound(a+1,a+1+n,b[i])-a;
memset(Great,0,sizeof Great);
for(int i=1;i<=n;i++)
{
Great[sum(b[i])]++;
add(b[i],1);
}
for(int i=0;i<=n-1;i++)
cout<<Great[i]<<endl;
}
好