记录编号	444162	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SYZOI Round1]滑稽♂树	最终得分	100
用户昵称	wumingshi	是否通过	通过
代码语言	C++	运行时间	2.935 s
提交时间	2017-09-02 11:04:16	内存使用	44.54 MiB

#include<cstdio>
const int N=2e5+10;
struct node
{
	int num,size,cnt;
	node *ch[2],*fa;
	inline int getwh(){return fa->ch[0]==this?0:1;}
	inline void update(){size=ch[0]->size+ch[1]->size+cnt;}
	inline void setch(int wh,node *child);
}pool[1500000],*t[N<<2],*null;
inline void node::setch(int wh,node *child)
{
	ch[wh]=child;
	if(child!=null) child->fa=this;
	update();
}
struct edge
{
	int nxt,to;
}e[N<<1];
int head[N],a[N],size[N],pos[N],s[N];
int n,m,opt,x,y,z,tot,cnt,num;
inline void add(int x,int y)
{
	e[++num].nxt=head[x],e[num].to=y,head[x]=num;
	e[++num].nxt=head[y],e[num].to=x,head[y]=num;
}
void dfs(int now,int fa)
{
	size[now]=1,pos[now]=++cnt;s[cnt]=a[now];
	for(int i=head[now];i;i=e[i].nxt)
	  if(e[i].to!=fa) dfs(e[i].to,now),size[now]+=size[e[i].to];
}
inline node *getnew(int value,bool normal)
{
	node *now=pool+ ++tot;
	now->ch[0]=now->ch[1]=now->fa=null;
	if(normal) now->size=now->cnt=1;
	now->num=value;
	return now;
}
inline void rotate(node *now)
{
	node *fa=now->fa,*grand=fa->fa;
	int wh=now->getwh();
	fa->setch(wh,now->ch[wh^1]);
	now->setch(wh^1,fa);
	now->fa=grand;
	if(grand!=null) grand->ch[grand->ch[0]==fa?0:1]=now;
	fa->update(),now->update(),grand->update();
}
inline void splay(node *now,node *tar,node *&root)
{
	for(;now->fa!=tar;rotate(now))
	  if(now->fa->fa!=tar) now->getwh()==now->fa->getwh()?rotate(now->fa):rotate(now);
	if(tar==null) root=now;
}
inline void insert(int value,node *&root,bool normal)
{
	node *now=root,*last=null;
	while(now!=null)
	{
		last=now;
		if(now->num==value){now->cnt++,now->size++,splay(now,null,root);return;}
		if(now->num>value) now=now->ch[0];
		else now=now->ch[1];
	}
	if(last==null){root=getnew(value,normal);return;}
	now=getnew(value,normal);
	if(last->num>value) last->setch(0,now);
	else last->setch(1,now);
	splay(now,null,root);
}
inline node *find(int value,node *&root)
{
	node *now=root;
 	while(now!=null)
	{
		if(now->num==value){splay(now,null,root);return now;}
		if(now->num>value) now=now->ch[0];
		else now=now->ch[1];
	}
}
inline void del(int value,node *&root)
{
	node *now=find(value,root);
	if(now->cnt>1){now->cnt--,now->size--,splay(now,null,root);return;}
	if(now->ch[0]==null&&now->ch[1]==null){root=null;return;}
	if(now->ch[0]==null){root=now->ch[1],root->fa=null;return;}
	if(now->ch[1]==null){root=now->ch[0],root->fa=null;return;}
	node *Root=now->ch[0];
	while(Root->ch[1]!=null) Root=Root->ch[1];
	splay(Root,now,root);
	Root->setch(1,now->ch[1]);
	Root->fa=null;
	root=Root;
}
inline int rank(int value,node *&root)
{
	int ans=0;node *now=root;
	while(now!=null)
	{
		if(now->num==value){ans+=now->ch[0]->size;splay(now,null,root);return ans;}
		if(now->num>value) now=now->ch[0];
		else ans+=now->ch[0]->size+now->cnt,now=now->ch[1];
	}
	return ans;
}
inline node *pre(int value,node *&root)
{
	node *now=root,*ans=null;
	while(now!=null)
	  if(now->num<value) ans=now,now=now->ch[1];
	  else now=now->ch[0];
	return ans;
}
inline node *nxt(int value,node *&root)
{
	node *now=root,*ans=null;
	while(now!=null)
	  if(now->num>value) ans=now,now=now->ch[0];
	  else now=now->ch[1];
	return ans;
}
inline int ask(int l,int r,node *&root)
{
	splay(pre(l,root),null,root);
	splay(nxt(r,root),root,root);
	return root->ch[1]->ch[0]->size;
}
inline void init(int l,int r,node *&root)
{
	root=null;
	insert(-1,root,0),insert(20000,root,0);
	for(int i=l;i<=r;i++)
	  insert(s[i],root,1);
}
void build(int l,int r,int now)
{
	init(l,r,t[now]);
	if(l==r) return;
	int mid=(l+r)>>1;
	build(l,mid,now<<1);
	build(mid+1,r,now<<1|1);
}
void change(int p,int l,int r,int now,int num)
{
	del(s[p],t[now]),insert(num,t[now],1);
	if(l==r) return;
	int mid=(l+r)>>1;
	if(p<=mid) change(p,l,mid,now<<1,num);
	else change(p,mid+1,r,now<<1|1,num);
}
int askrank(int L,int R,int l,int r,int now,int num)
{
	if(L<=l&&r<=R) return rank(num,t[now]);
	int mid=(l+r)>>1,ans=0;
	if(L<=mid) ans=askrank(L,R,l,mid,now<<1,num);
	if(R>mid) ans+=askrank(L,R,mid+1,r,now<<1|1,num);
	return ans;
}
inline int Rank(int l,int r,int num)
{
	int L=0,R=10001;
	while(L<R)
	{
		int mid=(L+R)>>1;
		if(askrank(l,r,1,n,1,mid)<num) L=mid+1;
		else R=mid;
	}
	return L-1;
}
inline int askval(int L,int R,int l,int r,int now,int x,int y)
{
	if(L<=l&&r<=R) return ask(x,y,t[now]);
	int mid=(l+r)>>1,ans=0;
	if(L<=mid) ans=askval(L,R,l,mid,now<<1,x,y);
	if(R>mid) ans+=askval(L,R,mid+1,r,now<<1|1,x,y);
	return ans;
}
int main()
{
	freopen("hjtree.in","r",stdin);
	freopen("hjtree.out","w",stdout);
	null=pool;
	null->ch[0]=null->ch[1]=null;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	  scanf("%d",&a[i]);
	for(int i=1;i<n;i++)
	  scanf("%d%d",&x,&y),add(x,y);
	dfs(1,0);build(1,n,1);
	scanf("%d",&m);int tmp=0;
	while(m--)
	{
		tmp++;
		scanf("%d%d%d",&opt,&x,&y);
		if(opt==1) printf("%d\n",Rank(pos[x],pos[x]+size[x]-1,y));
		else if(opt==2) scanf("%d",&z),printf("%d\n",askval(pos[x],pos[x]+size[x]-1,1,n,1,y,z));
		else change(pos[x],1,n,1,y),s[pos[x]]=y;
	}
	return 0;
}