HDU 3974 Assign the task(DFS + Segment Tree)

Description

N个点代表N个员工，形成一棵树，某点的父节点代表他的上司。公司分配任务时，若分配任务y给x，那么x的下属也会停止他们手头的任务来做任务y。

分配任务、查询某人在做哪个任务。

DFS序

①能将树的上各点的“父子关系”体现出来

②区间左端点是代表，左端点.val恰好能反应这个区间对应点的当前属性

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50010;

int n, m, pre[N], tot, in[N], out[N];
bool vis[N];
char s[10];

int cnt, head[N];
struct edge
{
    int v, nxt;
}e[N];

struct interval
{
    int L, R, val;
}a[N << 2 | 1];

void init()
{
    cnt = tot = 0;
    memset(head, -1, sizeof(head));
    memset(pre, -1, sizeof(pre));
    memset(vis, 0, sizeof(vis));
}

void add(int u, int v)
{
    e[cnt].v = v;
    e[cnt].nxt = head[u];
    head[u] = cnt++;
}

void DFS(int now)
{
    in[now] = ++tot;
    vis[now] = 1;
    for(int i = head[now]; ~i; i = e[i].nxt)
        if(!vis[ e[i].v ])
            DFS(e[i].v);
    out[now] = tot;
}

void build(int num, int l, int r)
{
    a[num].L = l;
    a[num].R = r;
    a[num].val = -1;

    if(l == r)
        return ;

    int mid = (l + r) >> 1;
    build(num << 1, l, mid);
    build(num << 1 | 1, mid + 1, r);
}

void down(int num)
{
    if(a[num].val != -1)
    {
        a[num << 1].val = a[num].val;
        a[num << 1 | 1].val = a[num].val;
        a[num].val = -1;
    }
}

void update(int num, int l, int r, int t)
{
    if(a[num].L > r || a[num].R < l)
        return ;
    if(a[num].L >= l && a[num].R <= r)
    {
        a[num].val = t;
        return ;
    }
    if(a[num].L == a[num].R)
        return ;

    down(num);
    update(num << 1, l, r, t);
    update(num << 1 | 1, l, r, t);
}

void query(int num, int p)
{
    if(a[num].L > p || a[num].R < p)
        return ;
    if(a[num].L == p && a[num].R == p)
    {
        cout << a[num].val << '\n';
        return ;
    }

    down(num);
    query(num << 1, p);
    query(num << 1 | 1, p);
}

int main()
{
    int _, t = 1;
    scanf("%d", &_);
    while(_--)
    {
        scanf("%d", &n);
        init();
        build(1, 1, n);
        int b, c;
        for(int i = 1; i <= n - 1; ++i)
        {
            scanf("%d%d", &b, &c);
            pre[b] = c;
            add(c, b);
        }
        for(int i = 1; i <= n; ++i)
            if(pre[i] == -1)
            {
                DFS(i);
                break;
            }

        cout << "Case #" << t++ << ":\n";

        int x, y;
        scanf("%d", &m);
        while(m--)
        {
            scanf("%s", s);
            if(s[0] == 'C')
            {
                scanf("%d", &x);
                query(1, in[x]);
            }
            else
            {
                scanf("%d%d", &x, &y);
                update(1, in[x], out[x], y);
            }
        }
    }
    return 0;
}
Copy
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

眼瞎Debug一个半小时