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

眼瞎Debug一个半小时