HDU - 3974 Assign the task （线段树区间修改+构建模型）

时间：2023-03-08 18:51:14
HDU - 3974 Assign the task （线段树区间修改+构建模型）

https://cn.vjudge.net/problem/HDU-3974

题意

有一棵树，给一个结点分配任务时，其子树的所有结点都能接受到此任务。有两个操作，C x表示查询x结点此时任务编号，T x y表示给x结点分配编号为y的任务。

分析

题目读起来就很有区间修改的味道，将一个区间变为一个值。问题在于怎么把这棵树对应到区间上。

对于一个结点，其控制的范围是它的子树，对应区间范围可以看作是以dfs序表示的区间。好像有点绕。。就是给每个结点再对应一个dfs序，然后在dfs时把这个点控制的子树看作是一段连续区间。然后就跑线段树啦。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <algorithm>

#include <cmath>

#include <ctime>

#include <vector>

#include <queue>

#include <map>

#include <stack>

#include <set>

#include <bitset>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

#define ms(a, b) memset(a, b, sizeof(a))

#define pb push_back

#define mp make_pair

#define pii pair<int, int>

#define eps 0.0000000001

#define IOS ios::sync_with_stdio(0);cin.tie(0);

#define random(a, b) rand()*rand()%(b-a+1)+a

#define pi acos(-1)

const ll INF = 0x3f3f3f3f3f3f3f3fll;

const int inf = 0x3f3f3f3f;

const int maxn = 5e4 + ;

const int maxm =  + ;

const int mod = ;

struct Edge{

    int to,nxt;

    Edge(){}

    Edge(int x,int y):to(x),nxt(y){}

}e[maxn];

int head[maxn],tot;

int cnt,start[maxn],ed[maxn];

void init(){

    tot=cnt=;

    memset(head,-,sizeof(head));

}

void addedge(int u,int v){

    e[tot]=Edge(v,head[u]);head[u]=tot++;

}

void dfs(int u){

    ++cnt;

    start[u]=cnt;

    for(int i=head[u];~i;i=e[i].nxt){

        dfs(e[i].to);

    }

    ed[u]=cnt;

}

struct ND{

    int l,r;

    int val,lazy;

}tree[maxn<<];

int n,m;

void pushup(int rt){

}

void pushdown(int rt){

    if(tree[rt].lazy){

        tree[rt<<].lazy=tree[rt<<|].lazy=tree[rt].lazy;

        tree[rt<<].val=tree[rt<<|].val=tree[rt].val;

        tree[rt].lazy=;

    }

}

void build(int rt,int l,int r){

    tree[rt].l=l,tree[rt].r=r;

    tree[rt].lazy=;

    tree[rt].val=-;

    if(l==r) return;

    int mid=(l+r)>>;

    build(rt<<,l,mid);

    build(rt<<|,mid+,r);

}

void update(int rt,int L,int R,int val){

    if(L<=tree[rt].l&&tree[rt].r<=R){

        tree[rt].val=val;

        tree[rt].lazy=;

        return;

    }

    pushdown(rt);

    int mid=(tree[rt].l+tree[rt].r)>>;

    if(mid>=L) update(rt<<,L,R,val);

    if(mid<R) update(rt<<|,L,R,val);

}

int query(int rt,int x){

    if(tree[rt].l==x&&tree[rt].r==x){

        return tree[rt].val;

    }

    pushdown(rt);

    int mid=(tree[rt].l+tree[rt].r)>>;

    if(mid>=x) return query(rt<<,x);

    else return query(rt<<|,x);

}

bool used[maxn];

int main() {

#ifdef LOCAL

    freopen("in.txt", "r", stdin);

//    freopen("output.txt", "w", stdout);

#endif

    int t,cas=;

    char op[];

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        printf("Case #%d:\n",cas++);

        init();

        int u,v;

        memset(used,false,sizeof(used));

        for(int i=;i<n;i++){

            scanf("%d%d",&u,&v);

            used[u]=true;

            addedge(v,u);

        }

        for(int i=;i<=n;i++)

            if(!used[i])

                dfs(i);

        build(,,cnt);

        scanf("%d",&m);

        while(m--){

            scanf("%s",op);

            if(op[]=='C'){

                scanf("%d",&u);

                printf("%d\n",query(,start[u]));

            }else{

                scanf("%d%d",&u,&v);

                update(,start[u],ed[u],v);

            }

        }

    }

    return ;

}

相关文章