由于经济不景气，小威的公司遭遇了空前的危机，为了能够顺利的度过这次危机，小威决定裁掉一部分能力比较差
的员工。如果一个员工的下属（包括直接下属或者间接下属）中有能力值超过他的，那么这个员工就称为比较差的
员工，这样的员工将被小威无情的炒掉。作为可能被炒鱿鱼的员工中的一员，小斌希望知道自己会不会被炒鱿鱼，
但是员工的人数实在太多，他无法正确的估计出自己将来的命运，所以他找到了你来帮助他。但是由于这件事实在
是太简单了，所以你决定额外实现两个功能：员工的能力值可以修改，实时询问某个员工是否会被炒鱿鱼。
Input
第一行，一个整数n，表示总共有多少个员工。
第二行到第n + 1 行，每行两个数，p，v，表示这个员工的直接上司是标号为p 的员工，他的能力值是v。
员工的编号为1~n，小威自己的编号为0，员工的信息按编号顺序输入。
接下来一行，一个数m，表示询问操作和修改操作的总次数。
接下来的m 行，每行一个操作，操作格式如下：
Q x 询问编号为x 的员工是否会被裁员
M p v 将编号为p 的员工的能力值改为v
Output
对于每一个询问操作输出一行，”Yes” 表示会被炒鱿鱼，”No” 表示不会被炒鱿鱼。
Sample Input
18
0 5
0 20
1 8
1 1
1 4
4 3
4 10
4 11
7 9
7 6
9 8
2 14
2 13
13 12
14 13
14 11
16 12
13 14
5
Q 1
M 1 50
Q 1
Q 11
Q 17
Sample Output
Yes
No
No
No
#include<map>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
int 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;
}
int root,n,m,cnt,size,top,ind;
int p[200005],v[200005],last[200005];
int mx[1600005],ls[1600005],rs[1600005];
int st[200005],inq[200005],ouq[200005],dfsq[400005];
bool mark[200005];
struct data
{
int to,next;
}e[200005];
void insert(int u,int v)
{
e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
}
void update(int k)
{
mx[k]=max(mx[ls[k]],mx[rs[k]]);
}
void modify(int &k,int l,int r,int pos,int val)
{
if(!k) //动态开点
k=++size;
if(l==r)
{
mx[k]=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)
modify(ls[k],l,mid,pos,val);
else
modify(rs[k],mid+1,r,pos,val);
update(k);
}
int query(int k,int l,int r,int x,int y)
{
if(!k)
return -inf;
if(l==x&&y==r)
return mx[k];
int mid=(l+r)>>1;
if(y<=mid)
return query(ls[k],l,mid,x,y);
else
if(x>mid)
return query(rs[k],mid+1,r,x,y);
else
return max(query(ls[k],l,mid,x,mid),query(rs[k],mid+1,r,mid+1,y));
}
void dfs()
{
st[++top]=0;
while(top)
{
int now=st[top];
if(mark[now])
{
ouq[now]=++ind;
dfsq[ind]=now;
top--;
continue;
}
else
{
mark[now]=1;
inq[now]=++ind;
dfsq[ind]=now;
}
for(int i=last[now];i;i=e[i].next)
st[++top]=e[i].to;
}
}
int main()
{
n=read();
mx[0]=-inf;
for(int i=1;i<=n;i++)
p[i]=read(),v[i]=read();
for(int i=1;i<=n;i++)
insert(p[i],i); //p[i]为i的父亲点
dfs();
for(int i=1;i<=n;i++)
modify(root,1,ind,inq[i],v[i]);
//在时间点inq[i]加入权值v[i]
m=read();
char ch[5];int x;
for(int i=1;i<=m;i++)
{
scanf("%s",ch+1);
x=read();
if(ch[1]=='Q')
{
int tmp=query(root,1,ind,inq[x],ouq[x]);
if(tmp>v[x])
puts("Yes");
else
puts("No");
}
else
{
v[x]=read();
modify(root,1,ind,inq[x],v[x]);
}
}
return 0;
}