HDU 3974 Assign the task（线段树 单点更新+lazy）

1 
5 
4 3 
3 2 
1 3 
5 2 
5 
C 3 
T 2 1
 C 3 
T 3 2 
C 3

Case #1:
-1 
1 
2

题意:先输入n个人，然后是n个人的关系(下属 上司)，然后分配任务，每一个上司分到一个任务就把任务给他的所有下属做，即她的下属的任务都是这个任务，任务不会平分，

查询一个人该时刻做的任务

思路:先找到树根，然后dfs求出每一个人控制的编号，然后每次查询时查询该人控制的下属范围，然后就是lazy，记录该人的任务是否已经传递下去了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>


#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

#define eps 1e-8
typedef __int64 ll;

#define fre(i,a,b)  for(i = a; i <b; i++)
#define free(i,b,a) for(i = b; i >= a;i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define ssf(n)      scanf("%s", n)
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf          printf
#define bug         pf("Hi\n")

using namespace std;

#define INF 0x3f3f3f3f
#define N 50005

int father[N],num;
vector<int>g[N];

int le[N],ri[N];

struct stud{
int le,ri;
int va;
int lazy;
}f[N*4];

int cha(int x)
{
	if(x!=father[x])
		father[x]=cha(father[x]);
	return father[x];
}

void dfs(int x)
{
    int i;
	le[x]=++num;

	fre(i,0,g[x].size())
	{
		dfs(g[x][i]);
	}
    ri[x]=num;
}

void pushdown(int pos)
{
	if(f[pos].va==-1) return ;
	if(f[pos].lazy==0) return ;

	f[L(pos)].va=f[pos].va;
	f[R(pos)].va=f[pos].va;
	f[L(pos)].lazy=f[R(pos)].lazy=1;
    f[pos].lazy=0;
}

void build(int pos,int le,int ri)
{
	f[pos].le=le;
	f[pos].ri=ri;
	f[pos].lazy=0;
	f[pos].va=-1;
	if(le==ri) return ;

	int mid=MID(le,ri);

	build(L(pos),le,mid);
	build(R(pos),mid+1,ri);
}

void update(int pos,int le,int ri,int va)
{
	if(f[pos].le==le&&f[pos].ri==ri)
	{
		f[pos].va=va;
		f[pos].lazy=1;
		return ;
	}

    pushdown(pos);

    int mid=MID(f[pos].le,f[pos].ri);

    if(mid>=ri)
		update(L(pos),le,ri,va);
	else
	 if(mid<le)
		update(R(pos),le,ri,va);
	else
	{
		update(L(pos),le,mid,va);
		update(R(pos),mid+1,ri,va);
	}
}

int query(int pos,int le)
{
	if(f[pos].le==le&&f[pos].ri==le)
		return f[pos].va;

	pushdown(pos);

	int mid=MID(f[pos].le,f[pos].ri);

	if(mid>=le)
		return query(L(pos),le);
    return query(R(pos),le);
}


int main()
{
	int i,j,t,m,n,ca=0;
	sf(t);
	while(t--)
	{
		sf(n);
		fre(i,1,n+1)
		{
			father[i]=i;
			g[i].clear();
		}
        int u,v;
        m=n-1;
        while(m--)
		{
			sff(u,v);
			father[u]=v;
			g[v].push_back(u);
		}

       u=cha(1);
       num=0;

       dfs(u);


       build(1,1,num);

       sf(m);

       pf("Case #%d:\n",++ca);

       char op[10];

       while(m--)
	   {
	   	  scanf("%s",op);
	   	  if(op[0]=='C')
		  {
		  	sf(u);
		  	pf("%d\n",query(1,le[u]));
		  }
          else
		  {
		  	 sff(u,v);
		  	 update(1,le[u],ri[u],v);
		  }
	   }
	}
	return 0;
}

HDU 3974 Assign the task（线段树 单点更新+lazy）

原文：http://blog.csdn.net/u014737310/article/details/44629815