HDU 1556.Color the ball[선분 수][4 월 28]

Color the ball
Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 15393    Accepted Submission(s): 7682
Problem Description
N 개의 풍선 이 한 줄 로 늘 어서 고 왼쪽 에서 오른쪽으로 순서대로 번호 가 1,2,3 이다.그런데 N 번 이후로 릴 은 I 번 째 풍선 이 몇 번 이나 발 랐 는 지 잊 어 버 렸 어 요.풍선 마다 몇 번 발 랐 는 지 계산 해 주 시 겠 어 요?
 
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
   
   
   
   

기본 라인 트 리:

#include<iostream>
#include<cstdio>
using namespace std;
const int MAX = 100010;
struct ss
{
    int left, right, value, mark;
}segtree[MAX*4];
int N, a, b, first;
void build(int root, int l, int r)
{
    segtree[root].left = l;
    segtree[root].right = r;
    if(l == r)
    {
        segtree[root].value = 0;
        segtree[root].mark = 0;
        return;
    }
    build(root*2, l, (l+r)/2);
    build(root*2+1, (l+r)/2+1, r);
    segtree[root].value = 0;
    segtree[root].mark= 0;
}
void add(int root, int l, int r)
{
    if(segtree[root].left > r || segtree[root].right < l) return;
    if(l <= segtree[root].left && r >= segtree[root].right)
    {
        segtree[root].mark ++;
        return;
    }
    add(root*2, l, r);
    add(root*2+1, l, r);
}
void answer(int root, int l, int r)
{
    if(l == r)
    {
        if(first == 0) cout <<" ";
        else first = 0;
        cout << segtree[root].value + segtree[root].mark;
        return;
    }
    segtree[root*2].mark += segtree[root].mark;
    segtree[root*2+1].mark += segtree[root].mark;
    answer(root*2, l, (l+r)/2);
    answer(root*2+1, (l+r)/2+1, r);
}
int main()
{
    while(scanf("%d", &N) != EOF && N)
    {
        first = 1;
        build(1, 1, N);
        for(int i = 0;i < N; ++i)
        {
            scanf("%d %d", &a, &b);
            add(1, a, b);
        }
        answer(1, 1, N);
        cout << endl;
    }
    return 0;
}