Problem Description

N个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？

Input

每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。

当N = 0，输入结束。

Output

每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。

Sample Input

3

1 1

2 2

3 3

3

1 1

1 2

1 3

0

Sample Output

1 1 1

3 2 1

code:

 

成段更新的一个技巧：每次更新区间【L,R】的时候不是在区间每个位置上都+1，而是只要在L 位置+1，在R+1 位置-1 ，每次求一个位置的值的时候，只要

                 求出从第一个位置到那个位置的和即可。

#include
       
         #include
        
          int l[100001]; int n; int lowbit(int x) { return (x)&(-x); } void update(int pos,int x) { while(pos<=n)     {         l[pos]+=x;         pos+=lowbit(pos);     } } int getsum(int x) { int sum=0; while(x>0)     {         sum+=l[x];         x-=lowbit(x);     } return sum; } int main() { int i,p,q; while(scanf("%d",&n),n)     {         memset(l,0,sizeof(l)); for(i=1;i<=n;i++)         {             scanf("%d%d",&p,&q);             update(p,1);             update(q+1,-1);         } for(i=1;i<=n;i++)             printf("%d%c",getsum(i),(i==n)?'\n':' ');     } return 0; }
        
       

普通做法：

#include
       
         #include
        
          int main() { int i,n,p,q,res; int l[100001]; while(scanf("%d",&n),n)  {   memset(l,0,sizeof(l)); for(i=1;i<=n;i++)   {    scanf("%d%d",&p,&q);    l[p]++;    l[q+1]--;   }   res=0; for(i=1;i