HD_1556Color the ball


                                                     Color the ball
                                                                     Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)                                                                      Total Submission(s): 13699    Accepted Submission(s): 6881
Problem Description
N 개의 풍선 이 한 줄 로 늘 어서 있 습 니 다. 왼쪽 에서 오른쪽으로 번호 가 1, 2, 3 입 니 다.
 
Input
각 테스트 실례 의 첫 번 째 행동 은 정수 N, (N < = 100000) 입 니 다. 다음 N 줄 은 정수 a b (1 < = a < = b < = N) 2 개 를 포함 합 니 다. 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
 
   
이것 은 전형 적 인 1 차원 나무 모양 배열 의 변형 이다. 일반적인 1 차원 나무 모양 배열 의 용 도 는 한 점 업데이트, 구간 값 을 구 하 는 것 이다. 이 문 제 는 나무 모양 배열 의 또 다른 용도 인 구간 업데이트, 한 점 으로 값 을 구 하 는 것 이다. 원 리 는 다음 과 같다.
     원시 배열 의 각 요 소 를 a [1], a [2],... a [n] 이 라 고 가정 하면 그러면 d [n] = a [1] + a [2] +. 
      그 다음 에 조금 만 바 꾸 고 원시 배열 의 각 요 소 를 a [1] - 0, a [2] - a [1], a [3] - a [2],..., a [n] - a [n - 1] 이 라 고 가정 하면 이때 의 n 항 과 d [n] = a [n], 즉 현재 원시 배열 의 n 항 과 d [n] 이다. 한 점 의 값 a [n] 와 같 습 니 다. 여러분, 여기 보시 면 좀 아 시 겠 죠?
      이어서 당신 이 생각 할 때 구간 [ a[m] …… a[n]  ] 모든 값 + Val, 원본 배열 의 m 항 (a [m] - a [m - 1]) Val 까지. ， n + 1 번 (a [n + 1] - a [n]) Val 을 빼 면 됩 니 다. 이렇게 m < = i < = n 일 때...
      수열 의 앞 i 항목 과:
      d[i] = (a[1] - 0) + (a[2] - a[1]) + (a[3] -a[2]) + …… + (a[m] - a[m - 1] + val) + (a[m + 1] - a[m]) + …… + (a[i] - a[i -1] )  = a[i]  + val 。  
      같은 이치 로 i > n 일 때 d [i] 는 원래 의 a [i] 와 같다. 。여기 보시 면 다 들 갑자기 밝 아 지 시 죠? 조심 하 세 요. 여기 a [1]... a [n] 의 초기 값 은 모두 0 입 니 다!! 코드 를 보십시오:

#include<stdio.h>
#include<string.h>

#define MAXN 100005

int C[MAXN];
int n;

int lowbit (int x)
{
    return x & (-x);
}

void add(int x , int d)
{
    while(x <= n)
    { 
        C[x] += d ;
        x += lowbit(x) ;
    } 
}

int sum(int x) 
{
    int sumt = 0 ;
    while (x > 0) 
    {
        sumt += C[x] ;
        x -= lowbit(x) ;
    }
    return sumt ;
} 

int main()
{
    while ((scanf("%d" , &n) != EOF),n) 
    {
        memset(C , 0 , sizeof(C)) ;
        int t = n ;
        while ( t-- )
        {
            int a , b ;
            scanf("%d%d", &a , &b) ;
            add(a ,+1) ;
            add(b +1,-1) ;
        } 
        for(int i = 1 ; i <= n ; i ++)  
        {
            printf((i==n?"%d
":"%d "), sum(i)) ;
        }
    }
    return 0 ;
}