题目已经说明了按Y值递增的顺序给出,Y值相同则按X递增给出。如果不是这样可以先排序,然后用树状数组解决。
以下是我的代码:
#include<cstdio>
#include<cstring>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kMaxn(15007);
const int kMaxx(32001);
int bit[kMaxx+7],level[kMaxn];
void Add(int pos,int delta)
{
for(int i=pos;i<=kMaxx;i+=lowbit(i))
bit[i]+=delta;
}
int Sum(int pos)
{
int re(0);
for(int i=pos;i>0;i-=lowbit(i))
re+=bit[i];
return re;
}
int main()
{
int n;
while(scanf("%d",&n)==1)
{
memset(bit,0,sizeof(bit));
memset(level,0,sizeof(level));
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
level[Sum(x+1)]++;
Add(x+1,1);
}
for(int i=0;i<n;i++)
printf("%d\n",level[i]);
}
return 0;
}
posted on 2011-07-31 10:19
lee1r 阅读(427)
评论(0) 编辑 收藏 引用 所属分类:
题目分类:数据结构