HDU 3974 DFS序 + 线段树区间更新

发表于 | 分类于 | 阅读次数：

将题目中的树结构稍微转变一下就是简单的线段树。

题目链接

题意

给你一个公司的上司与下属之间的关系，这样就形成了一个树，每次给一个人一个任务的时候，他的下属也会同时得到这个任务，而且必须立即停止之前的任务进行此时的这个任务，现在有两个操作，一是给某个人某个任务，而是询问某个人的此时正在执行的任务标号。

思路

一开始感觉没法处理这个树的关系，后来发现只要我们把每个人以他开始的团队的开始标号和结束标号都求出来，那么就是简单的线段树区间更新和单点查询了，这个标号需要利用DFS序来完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
using namespace std;
const int maxn = 100005;
struct edge{
   int v, next;
}edge[maxn];
int tot;
int head[maxn], vis[maxn];
void add(int u, int v)
{
    edge[++tot].v = v;
    edge[tot].next = head[u];
    head[u] = tot;
}
int start[maxn], ed[maxn];
void dfs(int rt)
{
    start[rt] = ++tot;
    for(int i = head[rt]; i != -1; i = edge[i].next)
    {
        dfs(edge[i].v);
    }
    ed[rt] = tot;
}
struct node{
   int lazy, num;
}tr[maxn << 2];

void pushdown(int node, int l, int r)
{
    if(tr[node].lazy == -1) return;
    tr[node << 1].lazy = tr[node << 1].num = tr[node].lazy;
    tr[node << 1|1].lazy = tr[node << 1|1].num = tr[node].lazy;
    tr[node].lazy = -1;
}
void build(int node, int l, int r)
{
    tr[node].num = -1;
    tr[node].lazy = -1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(node << 1, l, mid);
    build(node << 1|1, mid + 1, r);
}
void update(int node, int l, int r , int ql, int qr,int value)
{
    if(ql > r || qr < l) return;
    if(ql <= l && qr >= r)
    {
        tr[node].num = value;
        tr[node].lazy = value;
        return;
    }
    pushdown(node, l, r);
    int mid = (l + r) >> 1;
    update(node << 1, l, mid, ql, qr, value);
    update(node << 1|1,mid + 1, r, ql, qr, value);
}

int query(int node, int l, int r, int pos)
{
    if(l == r && l == pos)
    {
       return tr[node].num;
    }
    pushdown(node, l, r);
    int  mid = (l + r) >> 1;
    if(pos <= mid) query(node << 1, l, mid, pos);
    else query(node << 1|1, mid + 1, r, pos);
}
int main()
{
    int T,n,l,r,caser = 1;
    scanf("%d",&T);
    while(T--)
    {
        tot = 0;
        memset(vis, 0, sizeof(vis));
        memset(head, -1, sizeof(head));
        scanf("%d",&n);
        build(1,1,n);
        for(int i = 1; i <= n - 1; ++i)
        {
            scanf("%d %d",&l,&r);
            add(r,l);
            vis[l] = 1;
        }
        tot = 0;
        for(int i = 1; i <= n; ++i)
        {
            if(!vis[i])
            {
                dfs(i);
            }
        }
        int m,pos,value;
        scanf("%d",&m);
        cout << "Case #" << caser++ << ":" << '\n';
        while(m--)
        {
            string s;
            cin >> s;
            if(s[0] == 'C')
            {
                scanf("%d",&pos);
                cout << query(1,1,tot, start[pos]) << '\n';
            }
            else{
                scanf("%d %d",&pos,&value);
                update(1,1,tot,start[pos], ed[pos], value);
            }
        }
    }
}