樹狀數(shù)組的簡單題。
以下是我的代碼：
#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 閱讀(483)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)據(jù)結(jié)構(gòu)