【线段树区间更新】Count the Colors ZOJ - 1610

柔情只为你懂 2022-06-10 08:51 187阅读 0赞

Think:  
1知识点：线段树区间更新  
2题意：一条长度为8000的布条，每次输入xi, yi, ci, 表示将区间\[xi, yi\]染色为ci，询问最终状态每个颜色分别染了几段，按照index顺序输入  
3反思：  
1>左右儿子结点编号不要传入错误  
4思考：先将区间\[1, 8000\]全部初始化为-1, 之后输入xi, yi, ci之后将区间\[xi+1, yi\]颜色更新为ci, 更新完成后，进行区间\[1, 8000\]的颜色信息查询，将符合要求的每一段颜色信息存储到num数组中，最后进行总的判断输入即可

[vjudge题目链接][vjudge]

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 8014;
    
    struct Tree{
        int c;
    }tree[N<<2];
    
    int tmp, num[N];
    
    void add_v(int L, int R, int c, int l, int r, int rt);/*区间更新操作:将区间[L, R]颜色置为c*/
    void query(int l, int r, int rt);/*查询区间[l, r]的颜色信息，将需要信息存储到num数组中*/
    void down(int rt);/*将当前结点颜色信息down到左右儿子结点颜色信息*/
    
    int main(){
        int n, i, x, y, c;
        while(~scanf("%d", &n)){
            memset(tree, -1, sizeof(tree));
            memset(num, 0, sizeof(num));
            for(i = 0; i < n; i++){
                scanf("%d %d %d", &x, &y, &c);
                if(x < y)
                    add_v(x+1, y, c, 1, 8000, 1);/*区间查询从1开始，存储区间左结点右移一个单位*/
            }
            tmp = -1;
            query(1, 8000, 1);
            for(i = 0; i <= 8000; i++){
                if(num[i])
                    printf("%d %d\n", i, num[i]);
            }
            printf("\n");
        }
        return 0;
    }
    void add_v(int L, int R, int c, int l, int r, int rt){
        if(L <= l && r <= R){
            tree[rt].c = c;
            return;
        }
        down(rt);
        int mid = (l+r)/2;
        if(L <= mid)
            add_v(L, R, c, l, mid, rt<<1);
        if(R > mid)
            add_v(L, R, c, mid+1, r, rt<<1|1);
    }
    void down(int rt){
        if(tree[rt].c != -1){
            tree[rt<<1].c = tree[rt<<1|1].c = tree[rt].c;
            tree[rt].c = -1;
        }
    }
    void query(int l, int r, int rt){
        if(l == r){
            if(tree[rt].c != -1 && tree[rt].c != tmp)
                num[tree[rt].c]++;
            tmp = tree[rt].c;
            return;
        }
        down(rt);
        int mid = (l+r)/2;
        query(l, mid, rt<<1);
        query(mid+1, r, rt<<1|1);
    }

[vjudge]: https://vjudge.net/contest/163011#problem/F