记录编号	366858	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	黑白树的操作	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	11.472 s
提交时间	2017-01-26 10:08:06	内存使用	96.63 MiB

#include<cstdio>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
const int N=2e5+10;
typedef long long ll;
struct edge{int f,t,l;}w[N];
int head[N],tail[N],next[N];
void add(int f,int t,int l){
	static int cnt=0;
	w[++cnt]=(edge){f,t,l};
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
	w[++cnt]=(edge){t,f,l};
	if (!head[t]) head[t]=tail[t]=cnt;
		else tail[t]=next[tail[t]]=cnt;
}
ll dep[N];int Q[N],size,Size[N],vis[N];
set<int> son[N];
void vis_sub(int x){
	Q[++size]=x;
	for (set<int>::iterator i=son[x].begin();i!=son[x].end();++i) vis_sub(*i);
}
void dfs(int x,int fa){
	Q[++size]=x;
	for (int i=head[x];i;i=next[i])
	if (w[i].t!=fa){
		dep[w[i].t]=dep[x]+w[i].l;
		dfs(w[i].t,x);
	}
}
int T,n,m,fa[N],s[N],h[N];
ll sum[N],dis[N][50],up[N];
bool color[N];
void add(int p,int d){
	for (int x=p;x;x=fa[x]){
		s[x]+=d;
		sum[x]+=dis[p][h[x]]*d;
		if (fa[x]) up[x]+=dis[p][h[x]-1]*d;
	}
}
ll query(int x,int p){
	if (!fa[x]) return sum[x];
	return sum[x]+(s[fa[x]]-s[x])*dis[p][h[x]-1]-up[x]+query(fa[x],p);
}
int find(int x){return !fa[x]?x:find(fa[x]);}
int sub[N],big[N],Tree_size,root;
void getroot(int x,int Fa,int C){
	sub[x]=1;big[x]=0;
	for (int i=head[x];i;i=next[i]){
		int v=w[i].t;
		if (v==Fa||vis[v]!=C) continue;
		getroot(v,x,C);
		sub[x]+=sub[v];
		big[x]=max(big[x],sub[v]);
	}
	if (sub[x]>=Tree_size/2&&big[x]<=Tree_size/2) root=x;
}
void geth(int x,int Fa,int C,bool tp){
	if (color[x]) sum[root]+=dep[x];
	if (tp) dis[x][++h[x]]=dep[x],s[root]+=color[x];
	sub[x]=1;
	for (int i=head[x];i;i=next[i]){
		int v=w[i].t;
		if (v==Fa||vis[v]!=C) continue;
		dep[v]=dep[x]+w[i].l;
		geth(v,x,C,tp);
		sub[x]+=sub[v];
	}
}
void Set(int x,int Fa){
	if (fa[x]) son[fa[x]].erase(x);
	fa[x]=Fa;
	if (Fa) son[Fa].insert(x);
}
void build(int x,int C){
	s[x]=sum[x]=dep[x]=0;
	geth(x,0,C,1);
	vis[x]=0;
	Size[x]=sub[x];
	for (int i=head[x];i;i=next[i]){
		int v=w[i].t;
		if (vis[v]!=C) continue;
		sum[v]=0;root=v;geth(v,0,C,0);
		Tree_size=sub[v];
		getroot(v,0,C);
		Set(root,x);
		up[root]=sum[v];
		build(root,C);
	}
}
int main()
{
	freopen("MD5.in","r",stdin);
	freopen("MD5.out","w",stdout);
	//scanf("%d",&T); 
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) h[i]=Size[i]=1;
	char ch[5];int u,v,w;ll ans=0;
	while (m--){
		scanf("%s%d",ch,&u);
		u^=(ans%n+n)%n;
		if (ch[0]=='A'){
			scanf("%d%d",&v,&w);
			v^=(ans%n+n)%n;w^=(ans%n+n)%n;
			int Su=find(u),Sv=find(v);
			if (Size[Su]<Size[Sv]) swap(Su,Sv),swap(u,v);
			up[Sv]=query(v,v)+s[Sv]*w;
			Set(Sv,u);
			for (int x=u;x;x=fa[x]){
				Size[x]+=Size[Sv];
				s[x]+=s[Sv];
				sum[x]+=up[Sv]+s[Sv]*dis[u][h[x]];
				if (fa[x]) up[x]+=up[Sv]+s[Sv]*dis[u][h[x]-1];
			}
			dep[v]=w;size=0;dfs(v,0);
			add(u,v,w);
			int H=0;
			for (int i=1;i<=size;i++){
				int v=Q[i];
				for (int j=h[v];j;j--)
					dis[v][j+h[u]]=dis[v][j];
				H=max(H,h[v]+=h[u]);
				for (int j=1;j<=h[u];j++)
					dis[v][j]=dep[v]+dis[u][j];
			}
			int Tree=0;
			for (int x=u,last=Sv;x;last=x,x=fa[x])
				if (0.7*Size[x]+5<Size[last]) Tree=x;
			if (Tree){//重构 
				static int C=0;C++;
				size=0;vis_sub(Tree);
				int Fa=fa[Tree];
				for (int i=1;i<=size;i++)
					Set(Q[i],0),h[Q[i]]=h[Fa],vis[Q[i]]=C;
				Tree_size=size;
				getroot(Tree,0,C);
				Set(root,Fa);
				up[root]=up[Tree];
				build(root,C);
			}
		}
		if (ch[0]=='C') add(u,color[u]?-1:1),color[u]^=1; 
		if (ch[0]=='Q') printf("%lld\n",ans=query(u,u));
	}
	return 0;
}