记录编号	412370	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]黑树白	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.484 s
提交时间	2017-06-08 22:26:42	内存使用	351.25 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+10,M=3e7+10;
struct Node{int l,r,v;}node[M];int id;
int n,m,w[N],v[N],head[N],next[N];
void add(int f,int t){
	static int cnt=0;
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
int fa[N],s[N],big[N];
void dfs(int x){
	s[x]=1;
	for (int i=head[x];i;i=next[i])
	if (!fa[w[i]]){
		int v=w[i];
		fa[v]=x;
		dfs(v);
		s[x]+=s[v];
		if (s[v]>s[big[x]]) big[x]=v;
	}
}
int dfn[N],link[N];
void po(int x){
	static int cnt=0;
	dfn[x]=++cnt;
	link[x]=(dfn[x]==dfn[fa[x]]+1?link[fa[x]]:x);
	if (!big[x]) return;
	po(big[x]);
	for (int i=head[x];i;i=next[i])
	if (w[i]!=fa[x]&&w[i]!=big[x]) po(w[i]);
}
int add(int x,int l,int r,int p,int d){
	int now=++id;
	node[now]=node[x];
	node[now].v+=d;
	if (l==r) return now;
	int mid=(l+r)>>1;
	if (p>mid) node[now].r=add(node[x].r,mid+1,r,p,d);
		else node[now].l=add(node[x].l,l,mid,p,d);
	return now;
}
int query(int x,int l,int r,int L,int R){
	if (l>=L&&r<=R) return node[x].v;
	int mid=(l+r)>>1,ans=0;
	if (L<=mid) ans+=query(node[x].l,l,mid,L,R);
	if (R>mid) ans+=query(node[x].r,mid+1,r,L,R);
	return ans;
}
struct bit{
	int a[N];
	void add(int v,int p,int d){
		for (;v<=n;v+=v&-v) a[v]=::add(a[v],1,n,p,d);
	}
	int sum(int p,int l,int r){
		int ans=0;
		for (;p;p-=p&-p) ans+=::query(a[p],1,n,l,r);
		return ans;
	}
	int sum(int a,int b,int l,int r){
		return sum(b,l,r)-sum(a-1,l,r);
	}
}T;
int main()
{
	freopen("D_Tree.in","r",stdin);
	freopen("D_Tree.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&v[i]);
	for (int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	fa[1]=1;dfs(1);po(1);
	for (int i=1;i<=n;i++) T.add(v[i],dfn[i],1);
	int ans=0,x,y,a,b;
	char s[10];
	while (m--){
		scanf("%s%d%d",s,&x,&y);
		x=(x+ans)%n+1;
		y=(y+ans)%n+1;
		if (s[0]=='Q'){
			scanf("%d%d",&a,&b);
			ans=0;
			for (;link[x]!=link[y];x=fa[link[x]]){
				if (dfn[link[x]]<dfn[link[y]]) swap(x,y);
				ans+=T.sum(a,b,dfn[link[x]],dfn[x]);
			}
			if (dfn[x]>dfn[y]) swap(x,y);
			ans+=T.sum(a,b,dfn[x],dfn[y]);
			printf("%d\n",ans);
		}
		else{
			T.add(v[x],dfn[x],-1);
			T.add(v[x]=y,dfn[x],1);
		}
	}
	return 0;
}