心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
树状数组的简单题。
以下是我的代码:
#include<cstdio>
#include
<cstring>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kMaxn(100007);

int n,bit[kMaxn];

void Add(int x,int delta)
{
    
for(int i=x;i<=n;i+=lowbit(i))
        bit[i]
+=delta;
}

int Value(int x)
{
    
int re(0);
    
for(int i=x;i>0;i-=lowbit(i))
        re
+=bit[i];
    
return re;
}

int main()
{
    
//freopen("data.in","r",stdin);
    
    
while(scanf("%d",&n)==1 && n)
    {
        memset(bit,
0,sizeof(bit));
        
for(int i=1;i<=n;i++)
        {
            
int a,b;
            scanf(
"%d%d",&a,&b);
            Add(a,
1);
            Add(b
+1,-1);
        }
        
        
for(int i=1;i<=n;i++)
        {
            
if(i!=1)
                printf(
" ");
            printf(
"%d",Value(i));
        }
        printf(
"\n");
    }
    
    
return 0;
}
posted on 2011-08-01 22:42 lee1r 阅读(460) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:数据结构

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