记录编号	444919	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SYZOI Round1]滑稽♂树	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	3.717 s
提交时间	2017-09-04 17:52:46	内存使用	1.03 MiB

#include<cstdio>
#include<iostream>
#define mid_a ((l+r)>>1)
#define mid_b ((L+R)>>1)
const int maxn=30005;
using namespace std;
struct stree
{
	int cnt;
	stree *ls,*rs;
	stree(){cnt=0;ls=rs=NULL;}
}*roots[maxn];
struct edge
{
	int fr,to;
	edge *nt;
	edge(){fr=to=0;nt=NULL;}
}*e[maxn];
inline int get();
inline edge *add(int fr,int to);
void dfs(edge *now);
void insert(stree *&now,int v,int k,int l,int r);
inline void add_tree(int p,int v,int k);
inline int lowbit(int t);
int search(stree *now,int l,int r,int L,int R);
inline int kth(int l,int r,int k);
inline int S(int l,int r,int b,int c);
int n,q;
int wei[maxn],mx=10000,mi=1;
bool jud[maxn];
int dfsn,dfn[maxn],atdfn[maxn],leave[maxn];
int main()
{
	freopen("hjtree.in","r",stdin);
	freopen("hjtree.out","w",stdout);
	n=get();
	for(int i=1;i<=n;i++)wei[i]=get();
	for(int i=1;i<n;i++)
	{
		int u=get(),v=get();
		e[u]=add(u,v);
		e[v]=add(v,u);
	}
	dfs(e[1]);
	for(int i=1;i<=n;i++)add_tree(dfn[i],wei[i],1);
	q=get();
	for(int i=1;i<=q;i++)
	{
		int opt=get();
		if(opt==1)
		{
			int a=get(),b=get();
			printf("%d\n",kth(dfn[a],leave[a],b));
		}
		else if(opt==2)
		{
			int a=get(),b=get(),c=get();
			int l=dfn[a],r=leave[a];
			printf("%d\n",S(l,r,b,c));
		}
		else
		{
			int a=get(),b=get();
			add_tree(dfn[a],wei[a],-1);
			add_tree(dfn[a],wei[a]=b,1);
		}
	}
	return 0;
}
inline int S(int l,int r,int b,int c)
{
	register int sum=0;
	for(;r;r-=lowbit(r))sum+=search(roots[r],b,c,mi,mx);
	for(--l;l;l-=lowbit(l))sum-=search(roots[l],b,c,mi,mx);
	return sum;
}
inline int kth(int l,int r,int k)
{
	register int L=mi,R=mx;
	int ans,temp;
	while(L<=R)
		if((temp=S(l,r,mi,mid_b))>=k)ans=mid_b,R=mid_b-1;
		else L=mid_b+1;
	return ans;
}
int search(stree *now,int l,int r,int L,int R)
{
	if(!now)return 0;
	if(l==L&&r==R)return now->cnt;
	if(r<=mid_b)return search(now->ls,l,r,L,mid_b);
	else if(l>mid_b)return search(now->rs,l,r,mid_b+1,R);
	else return search(now->ls,l,mid_b,L,mid_b)+search(now->rs,mid_b+1,r,mid_b+1,R);
}
inline int lowbit(int t)
{
	return t&(-t);
}
inline void add_tree(int p,int v,int k)
{
	for(;p<=n;p+=lowbit(p))insert(roots[p],v,k,mi,mx);
}
void insert(stree *&now,int v,int k,int l,int r)
{
	if(!now)now=new stree();
	now->cnt+=k;
	if(l^r)
	{
		if(v<=mid_a)insert(now->ls,v,k,l,mid_a);
		else insert(now->rs,v,k,mid_a+1,r);
	}
}
void dfs(edge *now)
{
	int fr=now->fr;
	dfn[fr]=++dfsn;
	atdfn[dfsn]=fr;
	for(;now;now=now->nt)if(!dfn[now->to])dfs(e[now->to]);
	leave[fr]=dfsn;
}
inline edge *add(int fr,int to)
{
	edge *p=new edge();
	p->fr=fr;p->to=to;
	p->nt=e[fr];
	return p;
}
inline int get()
{
	int t=0;char j=1,c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')j=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		t=(t<<3)+(t<<1)+c-'0';
		c=getchar();
	}
	return j*t;
}