Color the ball

Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 7540    Accepted Submission(s): 3887

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

 

 

Author

8600

 

 

Source

 

 

Recommend

LL   |   We have carefully selected several similar problems for you:            

 

 

1 //390MS    1020K    720 B    C++ 2 //树状数组模板题，还有O(n)的简单算法，这里不贴。  3 #include
     
       4 #include
      
        5 #define N 100005 6 int c[N],d[N]; 7 int lowbit(int k) 8 { 9     return (-k)&k;10 }11 int getsum(int k)12 {13     int sum=0;14     while(k
       
        0){23         c[k]+=detal;24         k-=lowbit(k);25     }26 }27 int main(void)28 {29     int n,a,b;30     while(scanf("%d",&n),n)31     {32         memset(c,0,sizeof(c));33         memset(d,0,sizeof(d));34         for(int i=0;i