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

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <bitset>

using namespace std;

typedef long long LL;

void read(int &x) {
    char c;bool flag = 0;
    while((c=getchar())<'0'||c>'9') flag |= (c=='-');
    x=c-'0';while((c=getchar())>='0'&&c<='9') x = x*10+c-'0';
    flag?x=-x:x;
}

#define N 30100
#define W 10000
/////////////////////////////////////
struct E {
	int to,next;
	E(int to = 0,int next = 0):to(to),next(next){}
} g[N<<1];
int fr[N],tot,id[N],idd,n,w[N],siz[N],fa[N];
//
int M,rt[N*5];
//
int cnt;
struct Node{int lch,rch,sum;}t[N*200];
//
void AddE(int from,int to) {
	g[++tot] = E(to,fr[from]);
	fr[from] = tot;
}

void dfs(int t) {
	id[t] = ++idd; siz[t] = 1;
	for (int i = fr[t]; i; i = g[i].next) {
		int to = g[i].to;
		if(to == fa[t]) continue;
		fa[to] = t;
		dfs(to); siz[t] += siz[to];
	}
}
//////////////////////////////////////
void u2_add(int l,int r,int &o,int v,int x) {
	if(!o) o = ++cnt;
//cout<<l<<" "<<r<<" "<<o<<"\n";
	if(l == r) {t[o].sum += v; return;}
	int mid = (l+r)>>1;
	x <= mid ? u2_add(l,mid,t[o].lch,v,x):u2_add(mid+1,r,t[o].rch,v,x);
	t[o].sum = t[t[o].lch].sum + t[t[o].rch].sum;
}

int q2_sum(int l,int r,int o,int x,int y) {
	if(!o) return 0;
	if(x <= l && r <= y) return t[o].sum;
	int ans = 0,mid = (l+r)>>1;
	if(x <= mid) ans += q2_sum(l,mid,t[o].lch,x,y);
	if(y > mid) ans += q2_sum(mid+1,r,t[o].rch,x,y);
	return ans;
}

//
void build1() {
    for(M = 1; M <= n+1; M <<= 1);
    for(int i = 1; i <= M+n+1; ++i) rt[i] = i;
    cnt = M+n+1;
}

int sum(int l,int r,int L,int R,int ans = 0) {
//cout<<"S"<<l<<" "<<r<<" "<<L<<" "<<R<<"\n";
	for (l = M+l-1,r = M+r+1; l^r^1; l>>=1,r>>=1) {
		if(~l&1) ans += q2_sum(1,W,rt[l^1],L,R);
		if(r&1) ans += q2_sum(1,W,rt[r^1],L,R);
	}
	return ans;
}


int replace(int pos,int w1,int w2) {
	pos += M;
	while(pos) {
		if(w1!=-1) u2_add(1,W,rt[pos],-1,w1);
		u2_add(1,W,rt[pos],1,w2);
		pos >>= 1;
	}
}

int kth(int L,int R,int k) {
//cout<<"kth "<<L<<" "<<R<<" "<<k<<"\n";
	int ans,l = 1,r = W;
	for (;;) {
		if(r-l <= 1) {
		   ans = (sum(L,R,1,l)==k?l:r);
		   break;
		}
		int mid = (l+r)>>1;
		sum(L,R,1,mid) < k ? l = mid : r = mid;
	}
//cout<<sum(L,R,1,8);
	return ans;
}
//

int main() {
    freopen("hjtree.in","r",stdin);freopen("hjtree.out","w",stdout);
	read(n);int u,v,x,y;
	for (int i = 1; i <= n; ++i) read(w[i]);
	for (int i = 1; i < n; ++i) {
		read(u);  read(v);
		AddE(u,v); AddE(v,u);
	}
	dfs(1);	build1();
	for (int i = 1; i <= n; i++) replace(id[i],-1,w[i]);
//for (int i = 1; i <= n; i++) cout<<id[i]<<" ";
//puts("");
	int Q,cas; read(Q);
	for (int i = 1; i <= Q; i++) {
		read(cas); read(u); read(x);
		if(cas == 1) printf("%d\n",kth(id[u],id[u]+siz[u]-1,x));
		else if(cas == 2) read(y),printf("%d\n",sum(id[u],id[u]+siz[u]-1,x,y));
		else replace(id[u],w[u],x),w[u] = x;
	}
    return 0;
}
/*
5
3 4 6 1 2
1 2
1 3
3 4
3 5
7
3 4 5
3 5 7
1 3 3
*/