专题七：线段树 / 线段树

 

There is a company that has N employees(numbered from 1 to N),every employee in the company has a immediate boss (except for the leader of whole company).If you are the immediate boss of someone,that person is your subordinate, and all his subordinates are your subordinates as well. If you are nobody’s boss, then you have no subordinates,the employee who has no immediate boss is the leader of whole company.So it means the N employees form a tree.

The company usually assigns some tasks to some employees to finish.When a task is assigned to someone,He/She will assigned it to all his/her subordinates.In other words,the person and all his/her subordinates received a task in the same time. Furthermore,whenever a employee received a task,he/she will stop the current task(if he/she has) and start the new one.

Write a program that will help in figuring out some employee’s current task after the company assign some tasks to some employee.

InputThe first line contains a single positive integer T( T <= 10 ), indicates the number of test cases.

For each test case:

The first line contains an integer N (N ≤ 50,000) , which is the number of the employees.

The following N – 1 lines each contain two integers u and v, which means the employee v is the immediate boss of employee u(1<=u,v<=N).

The next line contains an integer M (M ≤ 50,000).

The following M lines each contain a message which is either

“C x” which means an inquiry for the current task of employee x

or

“T x y”which means the company assign task y to employee x.

(1<=x<=N,0<=y<=10^9)OutputFor each test case, print the test case number (beginning with 1) in the first line and then for every inquiry, output the correspond answer per line.Sample Input

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

Sample Output

Case #1:
-1 
1 
2

 

  • 题意
    • 给出一棵二叉树，结点种保存的值均为-1，并规定两种操作
    • C x 查询原始下标为x的结点保存的值是多少
    • T x y 将以x为根节点的子树的所有结点保存的权值修改为y
  • 题解
    • 很容易想到需要用线段树维护区间修改
    • 但是如果直接建树，那么下标之间的关系不足以构成一颗线段树（而只是一颗二叉树）
    • 而我们知道，线段树的一大特性是“连续”，而如何使得结点x以及以x结点为根节点的子树下标连续呢？
    • 就是用时间戳去代表以x为根结点的子树，以s[x]为起始，e[x]为结束的时间戳不仅满足“连续”，还满足线段树的“完全覆盖”
    • 这里的产生的时间戳长度为n，获得e[x]时不再将时间向后加，而是直接以当前时间为e[x]，这样才能更好地满足线段树的特性
    • 这样，我们就用1~n的时间戳建立起了一颗线段树，而每个结点x影响范围就是它的子树s[x]~e[x]
  • 代码 
    • #include<algorithm>
#include <iostream>
#include   <fstream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B) {
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B) {
	(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='-'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='-')?-1:1;
	ret=(c=='-')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
const int maxn=5e4+5;
int n,ans;
int s[maxn],e[maxn],vis[maxn],tot;
vector<int>G[maxn];
struct SegmentTree {
	int l,r;
	long long sum, add;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define add(x) tree[x].add
} tree[1000010*4];
void build(int p,int l,int r) {
	l(p)=l,r(p)=r;
	add(p)=-1;//注意初始化位置 
	if(l==r) {
		return ;
	}
	int mid=(l+r)/2;//只有这里的一半是直接用传入的l，r，但实际上这里的l，r就是下面的p.l,p.r
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
void spread(int p) {
	if(add(p)!=-1) {
		add(p*2) = add(p); //给左子节点打延迟标记
		add(p*2+1) = add(p);
		add(p) = -1;//清除节点p的标记,这里因为是单点查询，所以在清除标记后不需要对该区间进行保留值的操作 
	}
}
void change(int p,int l,int r,int d) {
	if(l<=l(p) && r>=r(p)) { //完成覆盖
		add(p)=d;//给节点打延迟标记
		return ;
	}
	spread(p); //下传延迟标记
	int mid=(l(p)+r(p))/2; //这里的中间是当前节点的中间（或者说是偏左的中间）位置
	if(l<=mid)change(p*2,l,r,d);
	if(r>mid)change(p*2+1,l,r,d);//注意这里不是非此即彼的关系
}
void ask(int p,int l,int r) {//l==r,单点查询 
	if(l==l(p) && r==r(p)){
		ans=add(p);
		return;
	}
	spread(p);
	int mid=(l(p)+r(p))/2;
	if(l <= mid) ask(p*2,l,r);//注意！这里对中间元素进行比较的是l不是tree[p].l
	else if(r > mid) ask(p*2+1,l,r);
}
void dfs(int u) {
	tot++;
	s[u]=tot;
	cout<<tot<<" ";
	for(int i=0;i<G[u].size();i++)dfs(G[u][i]);
	e[u]=tot;
	cout<<tot<<" ";
}
int main() {
	int t,q,u,v,x,y,o=1;
	char op[3];
	scanf("%d",&t);
	while(t--) {
		printf("Case #%d:\n",o++);
		memset(vis,0,sizeof vis);
		scanf("%d",&n);
		build(1,1,n);
		for(int i=1; i<=n; i++)G[i].clear();
		for(int i=1; i<n; i++) {
			scanf("%d%d",&u,&v);
			vis[u]=1;
			G[v].push_back(u);//题中v是u的boss 
		}
		///dfs序
		for(int i=1; i<=n; i++)
			if(!vis[i]) {//仅根节点不被标记 
				tot=0;
				dfs(i);
				break;
			}
		scanf("%d",&q);
		for(int i=0; i<q; i++) {
			scanf("%s",op);
			if(op[0]=='C') {
				scanf("%d",&x);
				ask(1,s[x],s[x]);//最左边子节点就是需要查询的点 
				printf("%d\n",ans);
			}
			if(op[0]=='T') {
				scanf("%d%d",&x,&y);
				change(1,s[x],e[x],y);
			}
		}
	}
	return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注