美文网首页
hdoj1556 Color the ball

hdoj1556 Color the ball

作者: 科学旅行者 | 来源:发表于2016-08-07 18:58 被阅读16次

    题目:

    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;
    }
    

    相关文章

      网友评论

          本文标题:hdoj1556 Color the ball

          本文链接:https://www.haomeiwen.com/subject/duplsttx.html