Posted on 2011-11-02 20:21
C小加 阅读(1495)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
我是用树状数组写的。
注意到题上数据已经排好序了，所以Y坐标直接不用考虑。先找出x坐标在i之前的点的数量r，则此点即为r级，然后更新此点。
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN=15003;
const int MAXXY=32003;
int c[MAXXY],solve[MAXN];
void Init()
{
memset(solve,0,sizeof(solve));
memset(c,0,sizeof(c));
}
int Lowbit(int x)
{
return x&(-x);
}
void Update(int i)
{
while(i<=MAXXY)
{
c[i]+=1;
i+=Lowbit(i);
}
}
int Sum(int i)
{
int s=0;
while(i>0)
{
s+=c[i];
i-=Lowbit(i);
}
return s;
}
int main()
{
Init();
int n;
cin>>n;
int a,b,r;
for(int i=0;i<n;i++)
{
cin>>a>>b;
r=Sum(a+1);
solve[r]++;
Update(a+1);
}
for(int i=0;i<n;i++)
{
cout<<solve[i]<<endl;
}
return 0;
}