记录编号	373407	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SYZOI Round1]滑稽♂树	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	4.137 s
提交时间	2017-02-21 06:22:32	内存使用	1.80 MiB

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <ctime>
#define Mem(a, v) memset(a, v, sizeof a)
#define Mcpy(a, b) memcpy(a, b, sizeof a)
using namespace std;
typedef long long LL;
const int maxn = 30010;
#define lc rt<<1
#define rc rt<<1|1
#define mid (((l)+(r))>>(1))
#define lson lc,l,mid
#define rson rc,mid+1,r
void qkin(int &res){
	int x,f=1; char ch;
	while(ch=getchar(),ch<'0'||ch>'9')if(ch=='-')f=-1;x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;res=x*f;
}
void read(int &A){ qkin(A); }
void read(int &A,int &B){ qkin(A),qkin(B); }
void read(int &A,int &B,int &C){ qkin(A),qkin(B),qkin(C); }
void read(int &A,int &B,int &C,int &D)
{ qkin(A),qkin(B),qkin(C),qkin(D); }

int n,len,head[maxn],m,w[maxn];
struct Edge
{
	int to,next;
}e[maxn*2];
void insert(int x,int y){
	e[++len].to = y;
	e[len].next = head[x];
	head[x] = len;  
}
int dfn[maxn],pos[maxn],cnt,ra[maxn];
void Dfs(int x){
	dfn[x] = ++cnt; pos[cnt] = x;
	for(int i = head[x]; i; i = e[i].next){
		int p = e[i].to;
		if(!dfn[p]) Dfs(p);
	}
	ra[x] = cnt;
}

#define siz(x) ((x)?((x)->size):(0))
struct node
{
	int data, size, key;
	node *ch[2];
	node(int d): data(d), size(1), key(rand()){}
	void ref(){ size=siz(ch[0])+siz(ch[1])+1; }
}*root[maxn*4];
node* newnode(int);
void insert(int,node*&);
void del(int,node*&);
void rot(node*&,int);
int rank(int,node*);

void insert(int i,int x,int rt,int l,int r){
	insert(x, root[rt]);
	if(l == r) return;
	if(i<=mid) insert(i,x,lson);
	else       insert(i,x,rson);
}
void del(int i,int x,int rt,int l,int r){
	del(x, root[rt]);
	if(l == r) return;
	if(i<=mid) del(i,x,lson);
	else       del(i,x,rson);
}
int getrank(int s,int t,int x,int rt,int l,int r){
	if(s<=l && t>=r) return rank(x, root[rt]);
	if(t<=mid) return getrank(s,t,x,lson);
	if(s> mid) return getrank(s,t,x,rson);
	return getrank(s,t,x,lson)+getrank(s,t,x,rson);
}
void Build_tree_in_tree(){
	for(int i = 1; i <= n; i ++ )
		insert(i, w[pos[i]], 1, 1, n);
}
void Query(int s,int t,int k){
	int l = 1, r = 10000, ans;
	while(l <= r){
		ans = (l + r) >> 1;
		if(getrank(s,t,ans,1,1,n)+1 <= k) l = ans+1;
		else r = ans-1;
	}//r
	printf("%d\n", r);
}
void Query(int s,int t,int a,int b){
	int ans = 0;
	ans += getrank(s, t, b+1, 1, 1, n);
	ans -= getrank(s, t, a, 1, 1, n);
	printf("%d\n", ans);
}
int main(){
#define HAHA LALA
#ifdef HAHA
	freopen("hjtree.in","r",stdin);
	freopen("hjtree.out","w",stdout);
#endif
	srand(time(NULL));
	read(n);
	for(int i = 1; i <= n; i ++ ) read(w[i]);
	for(int i = 1; i < n; i ++ ){
		int x,y; read(x, y); 
		insert(x, y); insert(y, x);
	}
	Dfs(1);
	Build_tree_in_tree();
	read(m);
	int op, u, a, b;
	while(m--){
		read(op, u, a);
		if(op == 2) read(b);
		if(op == 1)	Query(dfn[u], ra[u], a);
		else if(op == 2) Query(dfn[u], ra[u], a, b);
		else {
			del(dfn[u], w[u], 1, 1, n);
			insert(dfn[u], a, 1, 1, n);
			w[u] = a;
		}
	}
	return 0;
}
node* newnode(int x){
	node *y = new node(x); 
	y->ch[0] = y->ch[1] = NULL;
	return y;
}
void insert(int x,node* &rt){
	if(!rt){ rt = newnode(x); return; }
	else {
		int d = (x < rt->data);
		insert(x, rt->ch[d^1]);
		rt->ref();
		if(rt->ch[d^1]->key > rt->key) rot(rt, d);
	}
}
void del(int x,node* &rt){
	if(x == rt->data){
		if(rt->ch[0] && rt->ch[1]){
			int d = (rt->ch[0]->key > rt->ch[1]->key);
			rot(rt, d); del(x, rt->ch[d]);
		} else {
			node *y = NULL;
			if(rt->ch[0]) y=rt->ch[0];
			else y=rt->ch[1];
			delete rt; rt = y;
		}
	}
	else del(x, rt->ch[(x<rt->data)^1]);
	if(rt) rt->ref();
}
void rot(node* &x,int d){
	node *y = x->ch[d^1];
	x->ch[d^1] = y->ch[d];
	y->ch[d] = x;
	x->ref(); y->ref();
	x = y;
}
int rank(int x,node* rt){
	int d = 0;
	while(rt){
		if(x <= rt->data) rt=rt->ch[0];
		else {
			d += siz(rt->ch[0])+1;
			rt=rt->ch[1];
		}
	}
	return d;
}