记录编号	373414	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SYZOI Round1]滑稽♂树	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	5.103 s
提交时间	2017-02-21 06:36:50	内存使用	148.31 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=30010;
struct node{
	int sm;
	node *lc,*rc;
	node():sm(0){}
}null[maxn*450],*ptr=null,*root[maxn<<2];
void dfs(int);
void add(int,int,int);
void qsum(int,int,int);
void kth(int,int,int);
void add(int,int,node*&);
void qsum(int,int,node*);
vector<int>G[maxn];
int p[maxn],dfn[maxn],finish[maxn],tim=0;
int n,m,w[maxn],x,y,s,t,a,b,k,d,tmp;
int main(){
	freopen("hjtree.in","r",stdin);
	freopen("hjtree.out","w",stdout);
	null->lc=null->rc=null;
	fill(root,root+(maxn<<2),(node*)null);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	d=1;
	dfs(1);
	scanf("%d",&m);
	while(m--){
		scanf("%d%d",&d,&x);
		if(d==1){
			scanf("%d",&k);
			s=dfn[x];
			t=finish[x];
			kth(1,10000,1);
			printf("%d\n",tmp);
		}
		else if(d==2){
			scanf("%d%d",&a,&b);
			s=dfn[x];
			t=finish[x];
			tmp=0;
			qsum(1,10000,1);
			printf("%d\n",tmp);
		}
		else{
			d=-1;
			y=w[x];
			k=dfn[x];
			add(1,10000,1);
			scanf("%d",&y);
			d=1;
			add(1,10000,1);
			w[x]=y;
		}
	}
	return 0;
}
void dfs(int x){
	k=dfn[x]=++tim;
	y=w[x];
	add(1,10000,1);
	for(int i=0;i<(int)G[x].size();i++)if(G[x][i]!=p[x]){
		p[G[x][i]]=x;
		dfs(G[x][i]);
	}
	finish[x]=tim;
}
void add(int l,int r,int rt){
	add(1,n,root[rt]);
	if(l==r)return;
	int mid=(l+r)>>1;
	if(y<=mid)add(l,mid,rt<<1);
	else add(mid+1,r,rt<<1|1);
}
void qsum(int l,int r,int rt){
	if(a<=l&&b>=r){
		qsum(1,n,root[rt]);
		return;
	}
	int mid=(l+r)>>1;
	if(a<=mid)qsum(l,mid,rt<<1);
	if(b>mid)qsum(mid+1,r,rt<<1|1);
}
void kth(int l,int r,int rt){
	if(l==r){
		tmp=l;
		return;
	}
	int mid=(l+r)>>1;
	tmp=0;
	qsum(1,n,root[rt<<1]);
	if(k<=tmp)kth(l,mid,rt<<1);
	else{
		k-=tmp;
		kth(mid+1,r,rt<<1|1);
	}
}
void add(int l,int r,node *&rt){
	if(rt==null){
		rt=++ptr;
		rt->lc=rt->rc=null;
	}
	rt->sm+=d;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(k<=mid)add(l,mid,rt->lc);
	else add(mid+1,r,rt->rc);
}
void qsum(int l,int r,node *rt){
	if(rt==null)return;
	if(s<=l&&t>=r){
		tmp+=rt->sm;
		return;
	}
	int mid=(l+r)>>1;
	if(s<=mid)qsum(l,mid,rt->lc);
	if(t>mid)qsum(mid+1,r,rt->rc);
}
/*
5
3 4 6 1 2
1 2
1 3
3 4
3 5
7
1 1 4
2 1 1 5
3 4 5
1 1 4
2 3 3 6
3 5 7
1 3 3
*/