【线段树+dfs序】J - Assign the task HDU - 3974

怼烎@ 2022-06-10 10:49 137阅读 0赞

Think:  
1知识点：线段树+dfs序  
2题意：输入一棵关系树，两种操作，C操作(查询结点x正在进行的工作(初始工作默认为-1))，T操作(结点x及其下属开始进行y工作)  
3思路：通过dfs序将其转化为可以建为线段树的映射结点，进而进行线段树的查询和更新操作即可。（用每个节点的所包含的子节点段来当做线段树的节点，查找每个节点所包含的段可以用简单的DFS实现）  
4反思：lazy标记没有很好理解，在进行更新操作时候没有考虑到应该将lazy标记down下去更新

[vjudge题目链接][vjudge]

[建议参考博客][Link 1]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    #define MID int mid = (tree[rt].l+tree[rt].r)>>1;
    #define lson rt<<1
    #define rson rt<<1|1
    
    const int N = 51400;
    
    struct Tree{
        int l, r, task;
        int lazy;
    }tree[N<<2];
    
    int in[N], out[N], use[N];
    int indx;
    vector <int> G[N];
    
    void dfs(int k);/*dfs序*/
    void Build(int l, int r, int rt);
    void down(int rt);
    int Query(int p, int rt);
    void up_v(int L, int R, int task, int rt);
    
    int main(){
        int k = 1, T, n, Q, i, u, v, task;
        char st[14];
        scanf("%d", &T);
        while(T--){
            scanf("%d", &n);
            for(i = 1; i <= n; i++)
                G[i].clear();/*初始化*/
            memset(use, 0, sizeof(use));
            for(i = 1; i <= n-1; i++){
                scanf("%d %d", &u, &v);
                G[v].push_back(u);/*G[v]存储v的直系下属*/
                use[u] = 1;
            }
            indx = 0;
            for(i = 1; i <= n; i++){
                if(!use[i]){
       /*boss*/
                    dfs(i);
                    break;
                }
            }
            Build(1, n, 1);
            printf("Case #%d:\n", k++);
            scanf("%d", &Q);
            while(Q--){
                scanf("%s", st);
                if(st[0] == 'C'){
                    scanf("%d", &u);
                    printf("%d\n", Query(in[u], 1));/*in[u]为u在线段树中的位置*/
                }
                else if(st[0] == 'T'){
                    scanf("%d %d", &u, &task);
                    up_v(in[u], out[u], task, 1);/*区间[in[u], out[u]]为u及其下属所在线段树中的位置*/
                }
            }
        }
        return 0;
    }
    void dfs(int k){
        in[k] = ++indx;
        int i, len = G[k].size();
        for(i = 0; i < len; i++){
            dfs(G[k][i]);
        }
        out[k] = indx;
    }
    void Build(int l, int r, int rt){
        tree[rt].lazy = 0;
        tree[rt].l = l, tree[rt].r = r, tree[rt].task = -1;
        if(l == r)
            return ;
        MID;
        Build(l, mid, lson);
        Build(mid+1, r, rson);
    }
    void down(int rt){
        if(tree[rt].lazy){
            tree[lson].lazy = tree[rson].lazy = 1;
            tree[lson].task = tree[rson].task = tree[rt].task;
            tree[rt].lazy = 0;
        }
    }
    int Query(int p, int rt){
        if(tree[rt].l == tree[rt].r)
            return tree[rt].task;
        down(rt);
        MID;
        if(p <= mid)
            return Query(p, lson);
        else
            return Query(p, rson);
    }
    void up_v(int L, int R, int task, int rt){
        if(L <= tree[rt].l && tree[rt].r <= R){
            tree[rt].task = task;
            tree[rt].lazy = 1;
            return;
        }
        down(rt);/*标记更新*/
        MID;
        if(L <= mid)
            up_v(L, R, task, lson);
        if(R > mid)
            up_v(L, R, task, rson);
    }

[vjudge]: https://vjudge.net/problem/HDU-3974
[Link 1]: http://www.cnblogs.com/liuxin13/p/4680089.html