记录编号	279056	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]疯狂的魔法树	最终得分	100
用户昵称	Aglove	是否通过	通过
代码语言	C++	运行时间	1.804 s
提交时间	2016-07-08 19:31:23	内存使用	14.04 MiB

#define MAXN 200010UL
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define rep(i, x, y) for(int i = (x) ; i <= (y) ; ++ i)
#define der(i, x, y) for(int i = (x) ; i >= (y) ; -- i)
#define reg(i, x) for(int i = d[x] ; i != -1 ; i = sg[i].nt)
#define fir first
#define sec second
#define mp make_pair
#define pb push_back

using namespace std;

int n, m, blo, tot = 1, a, b, ans, val, nw, add[MAXN], pos[MAXN], vis[MAXN], fa[MAXN], c[MAXN];
vector <int> v[MAXN];
char s[10];

struct Graph {
	int d[MAXN], t;
	Graph() { memset(d, -1, sizeof(d)); }
	struct Edge { int hou, nt; } sg[MAXN<<1];
	void Add_edge(int x, int y) {
		sg[t] = (Edge){y, d[x]}, d[x] = t ++;
		return;
	}
}G, T;

bool cmp(const int &a, const int &b) {
	return c[a]<c[b];
}

void Get_block(int x, int _fa) {
	fa[x] = _fa;
	if(v[pos[_fa]].size()==blo) {
		++ tot, pos[x] = tot;
		T.Add_edge(pos[_fa], tot);
		v[tot].push_back(x);
	} else pos[x] = pos[_fa], v[pos[x]].push_back(x);
	for(int i = G.d[x] ; i != -1 ; i = G.sg[i].nt) {
		if(G.sg[i].hou==_fa) continue;
		Get_block(G.sg[i].hou, x);
	}
	return;
}

int Get_up(vector <int> &v, int val) {
	int L = 0, R = v.size()-1;
	if(c[v[0]]>val) return -1;
	int ret = -1;
	while(L<=R) {
		int mid = (L+R)>>1;
		if(c[v[mid]]<=val) L = mid+1, ret = mid;
		else R = mid-1;
	}
	return ret;
}

int Get_low(vector <int> &v, int val) {
	int L = 0, R = v.size()-1;
	if(c[v[R]]<val) return -1;
	int ret = -1;
	while(L<=R) {
		int mid = (L+R)>>1;
		if(c[v[mid]]>=val) ret = mid, R = mid-1;
		else L = mid+1;
	}
	return ret;
}

int Judge(int x) {
	if(vis[x]) {
		if(vis[x]>=a&&vis[x]<=b) return v[x].size();
		else return 0;
	}
	int L = Get_low(v[x], a-add[x]);
	int R = Get_up(v[x], b-add[x]);
	if(L==-1||R==-1) return 0;
	return R-L+1;
}

void Dfs_block(int x) {
	ans += Judge(x);
	for(int i = T.d[x] ; i != -1 ; i = T.sg[i].nt) Dfs_block(T.sg[i].hou);
	return;
}

void Dfs_point(int x) {
	if(c[x]+add[pos[x]]>=a&&c[x]+add[pos[x]]<=b) ++ ans;
	for(int i = G.d[x] ; i != -1 ; i = G.sg[i].nt) {
		int nxt = G.sg[i].hou;
		if(nxt==fa[x]) continue;
		if(pos[nxt]==pos[x]) Dfs_point(nxt);
		else Dfs_block(pos[nxt]);
	}
	return;
}

void Block_add(int x) {
	if(vis[x]) vis[x] += val;
	else add[x] += val;
	for(int i = T.d[x] ; i != -1 ; i = T.sg[i].nt) Block_add(T.sg[i].hou);
	return;
}

void Point_add(int x) {
	c[x] += val;
	for(int i = G.d[x] ; i != -1 ; i = G.sg[i].nt) {
		int nxt = G.sg[i].hou;
		if(nxt==fa[x]) continue;
		if(pos[nxt]==pos[x]) Point_add(nxt);
		else Block_add(pos[nxt]);
	}
	return;
}

void Block_modify(int x) {
	add[x] = 0, vis[x] = val;
	for(int i = T.d[x] ; i != -1 ; i = T.sg[i].nt) Block_modify(T.sg[i].hou);
	return;
}

void Point_modify(int x) {
	c[x] = val-add[pos[x]];
	for(int i = G.d[x] ; i != -1 ; i = G.sg[i].nt) {
		int nxt = G.sg[i].hou;
		if(nxt==fa[x]) continue;
		if(pos[nxt]==pos[x]) Point_modify(nxt);
		else Block_modify(pos[nxt]);
	}
	return;
}

void Push_down(int x) {
	int siz = v[x].size();
	rep(i, 0, siz-1) c[v[x][i]] = vis[x];
	vis[x] = 0;
	return;
}

int main() {
	freopen("H_Tree.in", "r", stdin);
	freopen("H_Tree.out", "w", stdout);
	int x, y;
	scanf("%d%d", &n, &m);
	
	rep(i, 1, n) scanf("%d", &c[i]);
	rep(i, 2, n) scanf("%d%d", &x, &y), G.Add_edge(x, y), G.Add_edge(y, x);
	blo = 250, pos[0] = 1, Get_block(1, 0);
	rep(i, 1, tot) sort(v[i].begin(), v[i].end(), cmp);
	
	while(m --) {
		scanf("%s", s);
		if(*s=='Q') {
			scanf("%d%d%d", &x, &a, &b);
			ans = 0, nw = pos[x];
			if(vis[nw]) Push_down(nw);
			Dfs_point(x); 
			printf("%d\n", ans);
		} else if(*s=='M') {
			scanf("%d%d", &x, &val);
			nw = pos[x];
			if(vis[nw]) Push_down(nw);
			c[x] = val-add[nw];
			sort(v[nw].begin(), v[nw].end(), cmp);
		} else if(*s=='C') {
			scanf("%d%d", &x, &val);
			nw = pos[x];
			if(vis[nw]) Push_down(nw);
			Point_add(x);
			sort(v[nw].begin(), v[nw].end(), cmp);
		} else if(*s=='W') {
			scanf("%d%d", &x, &val);
			nw = pos[x];
			if(vis[nw]) Push_down(nw);
			Point_modify(x);
			sort(v[nw].begin(), v[nw].end(), cmp);
		} else {
			int x, y;
			scanf("%d%d", &x, &y);
			++ n, fa[n] = x, c[n] = y;
			G.Add_edge(x, n);
			if(v[pos[x]].size()==blo) {
				++ tot, pos[n] = tot;
				T.Add_edge(pos[x], tot);
				v[tot].push_back(n);
			} else {
				nw = pos[x];
				if(vis[nw]) Push_down(nw);
				pos[n] = pos[x], c[n] = y-add[nw];
				v[nw].push_back(n);
				sort(v[nw].begin(), v[nw].end(), cmp);
			}
		}
	}
	return 0;
}