HDU 3974 (dfs序+线段树)

题意: 一个公司内共 n n n个人,给出这 n n n个人的上下级关系。一个人下属的下属也是他的下属。当一个人被分配了新的工作时,他的所有下属也将被分配这个新的工作(所有下属停止当前做的工作开始做新的工作)。每个人初始的工作为 1 -1 1 m m m次操作每次要么查询编号为 x x x人正在做的工作,要么更新一个人要做的工作(他的所有下属工作也将被更新)。

题解: d f s dfs dfs序求出一个人所有的下属,然后线段树区间更新单点查询即可。
忘初始化无限 R E RE RE,血和泪的教训~


#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 5e5 + 10, M = N;
int T, n, m;

bool isfa[N];
int h[N], e[M], ne[M], idx;
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int siz[N], dfn[N], tim;
void dfs(int u) {
	dfn[u] = ++tim;
	siz[u] = 1;
	for(int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];
		dfs(j);
		siz[u] += siz[j];
	}
}

struct Node{
	int l, r;
	int task, add;
}tr[N << 2];

void pushdown(int u) {
	Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
	if(root.add != -1) {
		left.task = left.add = root.add;
		right.task = right.add = root.add;
		root.add = -1;
	}
}

void build(int u, int l, int r) {
	tr[u] = {l, r, -1, -1};
	if(l == r) return ;
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);	
}

void modify(int u, int l, int r, int task) {
	if(tr[u].l >= l && tr[u].r <= r) {
		tr[u].task = tr[u].add = task;
		return ;
	}
	
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid) modify(u << 1, l, r, task);
	if(r > mid) modify(u << 1 | 1, l, r, task);
}

int query(int u, int x) {
	if(tr[u].l == tr[u].r) return tr[u].task;
	
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if(x <= mid) return query(u << 1, x);
	return query(u << 1 | 1, x);
}

void init(){
	idx = 0, tim = 0;
	memset(h, -1, sizeof h);
	memset(isfa, true, sizeof isfa);
}

int main()
{
	scanf("%d", &T);
	for(int k = 1; k <= T; k++) {
		printf("Case #%d:\n", k);
		
		init();
		scanf("%d", &n);
		for(int i = 1; i < n; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			add(b, a);
			isfa[a] = false;
		}
		
		int root = 0;
		for(int i = 1; i <= n; i++) 
			if(isfa[i]) {root = i; break;}
		
		dfs(root); 
		
		build(1, 1, n);
		
		scanf("%d", &m);
		while(m--) {
			char op[2]; int x, y;
			scanf("%s%d", op, &x);
			if(*op == 'C') printf("%d\n", query(1, dfn[x]));
			else {
				scanf("%d", &y);
				modify(1, dfn[x], dfn[x] + siz[x] - 1, y);
			}
		}
	}
	return 0;
}
全部评论

相关推荐

06-04 18:37
门头沟学院 Java
勇敢的ssr求对象:前面看的有点奔溃,看到只有你是真玩啊,忍不住笑出了声😂
点赞 评论 收藏
分享
只有一个苍穹外卖外加正在看黑马点评,可以找小厂实习吗,还有我的简历有什么大问题吗
Java抽象小篮子:感觉有点熟悉,问题1是学历,2是没实习经历,3是专业技能写得太少太少了(怎么写可以看我置顶帖),4是仅这一个项目找实习不够看。拷打完毕,简历怎么写可以看我置顶帖子
点赞 评论 收藏
分享
05-30 18:54
武汉商学院 Java
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
认真搞学习:28小登的建议,投算法岗不要写什么物理竞赛,互联网+,多写点项目,用什么算法做了什么。还有本科算法是不可能的开发你这个也没有项目啊
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务