HDU 3974 Assign the task 图论/线段树区间更新，单点查询

2019-11-06 08:17:54

字体：大中小

来源：转载

供稿：网友

题目链接:

http://acm.hdu.edu.cn/showPRoblem.php?pid=3974

题意:

给你一个树，v，u 表示u是v的上司有两个操作 1.让某一个点，和他的儿子们全部染成X 2.查询某一个点是什么颜色

题解:

当成图论跑一发，对于每一个查询直接跑到根位置就好，更新的时候，注意更新的时间问题

线段树也可以做：将树映射到区间的线段树。。。主要是将原有的关系树根据BOSS关系从新编号，以便把每个BOSS所带领的员工全部压入一个连续区间内，然后记录每个BOSS的起始编号和他的最后一名的员工的编号，然后用线段树区间更新，单点查找即可。

代码:

线段树：

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define MS(a) memset(a,0,sizeof(a))#define MP make_pair#define PB push_backconst int INF = 0x3f3f3f3f;const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//////////////////////////////////////////////////////////////////////////const int maxn = 5e4+10;int fa[maxn],cnt;int st[maxn],en[maxn];vector<int> g[maxn];void dfs(int u,int fa){ st[u] = ++cnt; for(auto v : g[u]){ dfs(v,u); } en[u] = cnt;}struct node{ int l,r,col;}tree[maxn<<2];void pushdown(int rt){ if(tree[rt].col!=-1){ tree[rt<<1].col = tree[rt<<1|1].col = tree[rt].col; tree[rt].col = -1; }}void build(int rt,int l,int r){ tree[rt].l = l, tree[rt].r = r; tree[rt].col = -1; if(l != r){ int mid = (l+r)/2; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); }}void update(int rt,int l,int r,int val){ int L = tree[rt].l, R = tree[rt].r; if(l<=L && R<=r){ tree[rt].col = val; return ; } pushdown(rt); int mid = (L+R)/2; if(l <= mid) update(rt<<1,l,r,val); if(r > mid) update(rt<<1|1,l,r,val);}int query(int rt,int p){ int L = tree[rt].l, R = tree[rt].r; if(L == R){ return tree[rt].col; } int mid = (L+R)/2; pushdown(rt); if(p <= mid) return query(rt<<1,p); else return query(rt<<1|1,p);}int main(){ int T = read(); for(int cas=1; cas<=T; cas++){ printf("Case #%d:/n",cas); int n = read(); MS(fa); for(int i=0; i<=n; i++) g[i].clear(); for(int i=1; i<n; i++){ int v=read(),u=read(); fa[v] = u; g[u].push_back(v); } cnt = 0; for(int i=1; i<=n; i++){ if(fa[i] == 0){ dfs(i,0); break; } } // cout << "hh " << cnt << endl; build(1,1,n); int m = read(); while(m--){ char op; scanf(" %c",&op); if(op == 'C'){ int u = read(); int ans = query(1,st[u]); printf("%d/n",ans); }else{ int u=read(),c=read(); update(1,st[u],en[u],c); } } } return 0;}

上一篇：IL指令详细表

下一篇：sizeof的理解