hdoj1556 Color the ball

题目：

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

其实此题可以用线段树来做：区间更新和单点查询。

参考代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100000+10;
struct node {
    int left,right;
    int lazy,max;
} e[N * 4];
void push_up(int p) {//比较两个子结点;
    e[p].max = max(e[p*2].max, e[p*2+1].max);
}
void push_down(int p) {
    if (e[p].lazy != 0) {//延迟标记;//将更新区间的值加在区间上，待查询和更新时才分解到区间的两个子结点;
        e[p*2].lazy += e[p].lazy;
        e[p*2].max += e[p].lazy;
        e[p*2+1].lazy += e[p].lazy;
        e[p*2+1].max += e[p].lazy;
        e[p].lazy = 0;
    }
}
void build(int p,int l,int r) {
    e[p].left = l;
    e[p].right = r;
    e[p].lazy = 0;
    if (l == r) {
        e[p].max = 0;//开始时都没有涂色;
    }
    else {
        int mid = (l + r) / 2;
        build(p*2,l,mid);
        build(p*2+1,mid+1,r);
        push_up(p);
    }
}
void update(int p,int l,int r,int val) {
    if (l <= e[p].left && e[p].right <= r) {
        e[p].lazy += val;
        e[p].max += val;
    }
    else {
        push_down(p);
        int mid = (e[p].left+e[p].right) / 2;
        if (l <= mid) update(p*2,l,r,val);
        if (r > mid) update(p*2+1,l,r,val);
        push_up(p);
    }
}
int query(int p,int l,int r) {
    if (l <= e[p].left && e[p].right <= r) {
        return e[p].max;
    }
    int mid = (e[p].left+e[p].right) / 2;
    push_down(p);
    int ans = 0;
    if (l <= mid) ans = max(ans, query(p*2,l,r));
    if (r > mid) ans = max(ans, query(p*2+1,l,r));
    return ans;
}
int n;
int main() {
    while (scanf("%d", &n) != EOF && n) {
        int a,b;
        build(1,1,n);
        for (int i = 1;i <= n;++i) {
            scanf("%d%d", &a, &b);
            update(1,a,b,1);
        }
        for (int i = 1;i <= n;++i) {
            int ans = query(1,i,i);
            if (i > 1)
                printf(" ");
            printf("%d", ans);
        }
        printf("\n");
    } 
    return 0;
}