心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
题目已经说明了按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)  编辑 收藏 引用 所属分类: 题目分类:数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理