407
hdu 1556 Color the ball 樹狀數組
最基本的樹狀數組，成段更新，感覺隻要構造的時候保證兩端平衡，即對後麵非更新地方無影響即可，所以這題是a++ (b+1)--
溫習了下快速IO，速度果然提升1倍
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int c[100005],n;
inline int low(int x)
{
return x&-x;
}
int update(int pos,int num)
{
while(pos<=n)
{
c[pos]+=num;
pos+=low(pos);
}
}
int query(int pos)
{
int ans=0;
while(pos>0)
{
ans+=c[pos];
pos-=low(pos);
}
return ans;
}
void input(int &n)
{
n=0;
int ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')
n=(n<<3)+(n<<1)+ch-'0',ch=getchar();
}
int main()
{
while(~scanf("%d",&n),n)
{
memset(c,0,sizeof(c));
int i,a,b;
for(i=0;i<n;i++)
{
input(a);input(b);
update(a,1);update(b+1,-1);
}
for(i=1;i<n;i++)
printf("%d ",query(i));
printf("%d\n",query(n));
}
}
最後更新：2017-04-03 16:48:44