LCT 题目选做

发表于

维护链信息

P1501 [国家集训队]Tree II

Solution

利用 $LCT$ 维护链上信息的经典题。

由于同时涉及到了加法和乘法，根据做线段树的经验，我们知道乘法优先，加法靠后。

剩余的普通的 $LCT$ 没什么区别。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int N = 1e5+5,mod = 51061;
int n,m,u,v,x,y,val[N],sz[N],tag1[N],tag2[N];
char opt[2],rev[N];
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
it mul(int x,int y){return 1ll*x*y%mod;}
il inc(int &x,int y){x=add(x,y);}
int ch[N][2],f[N],s[N],stk[N];
#define lc ch[x][0]
#define rc ch[x][1]
inl bool Not_root(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
il pushup(int x){
	s[x]=add(add(s[lc],s[rc]),val[x]);
	sz[x]=sz[lc]+sz[rc]+1;
}
il pushrev(int x){swap(lc,rc),rev[x]^=1;}
il pushmul(int x,int k){
	s[x]=mul(s[x],k),val[x]=mul(val[x],k);
	tag1[x]=mul(tag1[x],k),tag2[x]=mul(tag2[x],k);
}
il pushadd(int x,int k){
	inc(s[x],mul(k,sz[x])),inc(val[x],k);
	inc(tag2[x],k);
}
il pushdown(int x){
	if(tag1[x]!=1) pushmul(lc,tag1[x]),pushmul(rc,tag1[x]),tag1[x]=1;
	if(tag2[x]) pushadd(lc,tag2[x]),pushadd(rc,tag2[x]),tag2[x]=0;
	if(rev[x]){
		if(lc) pushrev(lc);
		if(rc) pushrev(rc);
		rev[x]=0;
	}
}
il Rotate(int x){
	int y=f[x],z=f[y],k=ch[y][1]==x,w=ch[x][!k];
	if(Not_root(y)) ch[z][ch[z][1]==y]=x;
	ch[x][!k]=y,ch[y][k]=w;
	if(w) f[w]=y;
	f[x]=z,f[y]=x,pushup(y);
}
il Splay(int x){
	int y=x,top=0;
	stk[++top]=y;
	while(Not_root(y)) stk[++top]=y=f[y];
	while(top) pushdown(stk[top--]);
	while(Not_root(x)){
		int y=f[x],z=f[y];
		if(Not_root(y)) Rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
		Rotate(x);
	}
	pushup(x);
}
il Access(int x){
	for(ri y=0;x;x=f[y=x])
		Splay(x),rc=y,pushup(x);
}
il Make_root(int x){Access(x),Splay(x),pushrev(x);}
il Split(int x,int y){Make_root(x),Access(y),Splay(y);}
il Link(int x,int y){Make_root(x),f[x]=y;}
il Cut(int x,int y){Split(x,y),f[x]=ch[y][0]=0,pushup(y);}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=n;++i)
		val[i]=sz[i]=tag1[i]=1;
	for(ri i=1;i<n;++i){
		read(u),read(v);
		Link(u,v);
	}
	for(ri i=1;i<=m;++i){
		scanf("%s",opt);
		if(opt[0]=='+'){
			read(u),read(v),read(x);
			Split(u,v),pushadd(v,x);
		}
		if(opt[0]=='-'){
			read(u),read(v),read(x),read(y);
			Cut(u,v),Link(x,y);
		}
		if(opt[0]=='*'){
			read(u),read(v),read(x);
			Split(u,v),pushmul(v,x);
		}
		if(opt[0]=='/'){
			read(u),read(v);
			Split(u,v),print(s[v]),puts("");
		}
	}
	return 0;
}

P3203 [HNOI2010]弹飞绵羊

Solution

我们将每个点向跳到的点连边，跳出的点向虚拟节点 $n+1$ 连边，可以发现一定构成了一棵树。

每次查询时，将 $u$ 到 $n+1$ 的链从原图中抽出来，那么答案就是 $sz-1$ 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int N = 2e5+5;
int n,m,opt,x,val[N];
int ch[N][2],f[N],sz[N],stk[N];
char rev[N];
#define lc ch[x][0]
#define rc ch[x][1]
inl bool Not_root(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
il pushup(int x){sz[x]=sz[lc]+sz[rc]+1;}
il pushrev(int x){swap(lc,rc),rev[x]^=1;}
il pushdown(int x){
	if(rev[x]){
		if(lc) pushrev(lc);
		if(rc) pushrev(rc);
		rev[x]=0;
	}
}
il Rotate(int x){
	int y=f[x],z=f[y],k=ch[y][1]==x,w=ch[x][!k];
	if(Not_root(y)) ch[z][ch[z][1]==y]=x;
	ch[x][!k]=y,ch[y][k]=w;
	if(w) f[w]=y;
	f[x]=z,f[y]=x,pushup(y);
}
il Splay(int x){
	int y=x,top=0;
	stk[++top]=y;
	while(Not_root(y)) stk[++top]=y=f[y];
	while(top) pushdown(stk[top--]);
	while(Not_root(x)){
		int y=f[x],z=f[y];
		if(Not_root(y)) Rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
		Rotate(x);
	}
	pushup(x);
}
il Access(int x){
	for(ri y=0;x;x=f[y=x])
		Splay(x),rc=y,pushup(x);
}
il Make_root(int x){Access(x),Splay(x),pushrev(x);}
il Split(int x,int y){Make_root(x),Access(y),Splay(y);}
il Link(int x,int y){Make_root(x),f[x]=y;}
il Cut(int x,int y){Split(x,y),f[x]=ch[y][0]=0,pushup(y);}
it Query(int x){
	Split(x,n+1);
	return sz[n+1]-1;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n);
	for(ri i=1;i<=n+1;++i) sz[i]=1;
	for(ri i=1;i<=n;++i)
		read(val[i]),Link(i,min(n+1,i+val[i]));
	read(m);
	for(ri i=1;i<=m;++i){
		read(opt),read(x),++x;
		if(opt==1) print(Query(x)),puts("");
		if(opt==2){
			Cut(x,min(n+1,x+val[x]));
			read(val[x]);
			Link(x,min(n+1,x+val[x]));
		}
	}
	return 0;
}

P4332 [SHOI2014]三叉神经树

Solution

我们通过观察可以发现一个有趣的情况：

  • 若是从 $0\rightarrow 1$ ，且 $x$ 指向的点的值为 $1$ ，那么会同它一起加 $1$ 的，只有到根结点的链上的连续的一段值为 $1$ 的点和最上方的点的父节点。
  • 同理，从 $1\rightarrow 0$ ，且指向的点值为 $2$ ，减 $1$ 的连续段的值均为 $2$ 。

其他情况只需要单点加减即可。

判断一个序段中所有元素的值是否相等，我们可以通过这样的方法来做：

判断左半边的值是否等于右半边的值，如果相等，那么这一段的值和左右半边的值相等，否则设为极大值。

至于修改只需要区间修改即可。

那么剩下的问题就是怎么找出这一个连续段。

我们设计一个倍增算法，假设当前点为 $s$ ，当前是 $2^p$ 。

  • 若存在 $fa[s][p]$ ，且 $s\rightarrow fa[s][p]$ 的值等于 $2/1$ ，那么另 $s=fa[s][p],p++$ 。
  • 否则 $p—$ 。

初始条件为 $s=u,p=0$ ，终止条件为 $p=-1$ 。

这样我们就解决了这道题。

$LCT$ 时间复杂度： $O(n\log^2n)$ 。

树剖时间复杂度： $O(n\log^3n)$ 。

Code

由于当时还不太熟练，所以写了复杂度贼大的树剖

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int N = 5e5+5;
int n,m,x,a[N],val[N<<1],fa[N][23],bl[N<<1];
vector<int> G[N];
il DFS(int u){
	for(auto v:G[u]){
		DFS(v);
		a[u]+=a[v]>=2;
	}
}
il Init(){
	for(ri i=1;i<=22;++i)
		for(ri j=1;j<=n;++j)
			fa[j][i]=fa[fa[j][i-1]][i-1];
}
int f[N],son[N],dep[N],sz[N],top[N],id[N],rk[N],cnt;
il DFS1(int u,int fa){
	f[u]=fa,sz[u]=1,dep[u]=dep[fa]+1;
	for(auto v:G[u]){
		DFS1(v,u),sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u]=v;
	}
}
il DFS2(int u,int t){
	top[u]=t,id[u]=++cnt,rk[cnt]=u;
	if(son[u]) DFS2(son[u],t);
	for(auto v:G[u]){
		if(v==son[u]) continue;
		DFS2(v,v);
	}
}
#define lc (cur<<1)
#define rc (cur<<1|1)
struct Seg_Tree{
	int tag,val;
}T[N<<2];
il pushup(int cur){T[cur].val=T[lc].val==T[rc].val?T[lc].val:5;}
il pushdown(int cur){
	if(T[cur].tag==-1) return ;
	T[lc].tag=T[cur].tag,T[lc].val=T[cur].tag;
	T[rc].tag=T[cur].tag,T[rc].val=T[cur].tag;
	T[cur].tag=-1;
}
il Build(int cur,int l,int r){
	T[cur].tag=-1;
	if(l==r) return T[cur].val=a[rk[l]],void();
	Build(lc,l,mid),Build(rc,mid+1,r);
	pushup(cur);
}
il Updata(int cur,int l,int r,int L,int R,int k){
	if(l>=L&&r<=R) return T[cur].val=T[cur].tag=k,void();
	pushdown(cur);
	if(mid>=L) Updata(lc,l,mid,L,R,k);
	if(R>mid) Updata(rc,mid+1,r,L,R,k);
	pushup(cur);
}
it Query(int cur,int l,int r,int L,int R){
//	printf("l=%d r=%d L=%d R=%d\n",l,r,L,R);
	if(l==L&&r==R) return T[cur].val;
	pushdown(cur);
	if(mid>=R) return Query(lc,l,mid,L,R);
	if(L>mid) return Query(rc,mid+1,r,L,R);
	int a=Query(lc,l,mid,L,mid),b=Query(rc,mid+1,r,mid+1,R);
//	printf("l=%d mid=%d r=%d a=%d b=%d\n",l,mid,r,a,b);
	return a==b?a:5;
}
il Updata_Path(int u,int v,int k){
//	printf("u=%d v=%d k=%d\n",u,v,k);
	while(top[u]^top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		Updata(1,1,n,id[top[u]],id[u],k);
		u=f[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	Updata(1,1,n,id[u],id[v],k);
}
it Query_Path(int u,int v,int k){
	int res=k;
	while(top[u]^top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		int t=Query(1,1,n,id[top[u]],id[u]);
		res=res==t?res:5;
		u=f[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	int t=Query(1,1,n,id[u],id[v]);
	return res==t?res:5;
}
il Solve(int u,int k){
	int p=0,v=u;
	while(p!=-1){
		if(!fa[u][p]){--p;continue;}
		int t=Query_Path(u,fa[u][p],k);
		if(t==k) u=fa[u][p],++p;
		else --p;
	}
	Updata_Path(u,v,k==2?1:2);
	if(fa[u][0]){
		int t=Query(1,1,n,id[fa[u][0]],id[fa[u][0]]);
		Updata(1,1,n,id[fa[u][0]],id[fa[u][0]],k==2?t-1:t+1);
	}
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n);
	for(ri i=1;i<=n;++i){
		for(ri j=1;j<=3;++j){
			read(x);
			if(x<=n) G[i].push_back(x),fa[x][0]=i;
			else bl[x-n]=i;
		}
	}
	for(ri i=1;i<=2*n+1;++i)
		read(val[i]),a[bl[i]]+=val[i];
	DFS(1),Init();
	DFS1(1,0),DFS2(1,1),Build(1,1,n);
	read(m);
	for(ri i=1;i<=m;++i){
		read(x),x-=n,a[bl[x]]=Query(1,1,n,id[bl[x]],id[bl[x]]);
		if(val[x]==1){
			if(a[bl[x]]==2) Solve(bl[x],2);
			else --a[bl[x]],Updata(1,1,n,id[bl[x]],id[bl[x]],a[bl[x]]);
		}
		else{
			if(a[bl[x]]==1) Solve(bl[x],1);
			else ++a[bl[x]],Updata(1,1,n,id[bl[x]],id[bl[x]],a[bl[x]]);
		}
		val[x]^=1;
		int t=Query(1,1,n,1,1);
		print(t<=1?0:1),puts("");
	}
	return 0;
}

动态维护连通性&&双连通分量

P2542 [AHOI2005]航线规划

Solution

断边不好维护，但是加边很好维护。

题目要求的是两点之间桥的数量，其实就是求路径上包好的边双连通分量的个数减 $1$ 。

我们向里面加边时，如果两点已经连通，我们就将路径上的边双连通分量全部缩为一个点。

用并查集维护每一个点所在边双，每次查询都需要找到对应的编号。

还有就是在 $Access$ 的时候也需要 $find$ 一下。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int N = 4e4+5;
int n,m,q,u,v,opt,x,y,fa[N],ans[N],num;
it find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
struct Edge{
	int u,v,vis;
}edge[N*3];
map<pair<int,int>,int> mp;
struct Node{
	int opt,x,y;
}node[N];
int ch[N][2],f[N],sz[N],stk[N];
char rev[N];
#define lc ch[x][0]
#define rc ch[x][1]
inl bool Not_root(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
il pushup(int x){sz[x]=sz[lc]+sz[rc]+1;}
il pushrev(int x){swap(lc,rc),rev[x]^=1;}
il pushdown(int x){
	if(rev[x]){
		if(lc) pushrev(lc);
		if(rc) pushrev(rc);
		rev[x]=0;
	}
}
il Rotate(int x){
	int y=f[x],z=f[y],k=ch[y][1]==x,w=ch[x][!k];
	if(Not_root(y)) ch[z][ch[z][1]==y]=x;
	ch[x][!k]=y,ch[y][k]=w;
	if(w) f[w]=y;
	f[x]=z,f[y]=x,pushup(y);
}
il Splay(int x){
	int y=x,top=0;
	stk[++top]=y;
	while(Not_root(y)) stk[++top]=y=f[y];
	while(top) pushdown(stk[top--]);
	while(Not_root(x)){
		int y=f[x],z=f[y];
		if(Not_root(y)) Rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
		Rotate(x);
	}
	pushup(x);
}
il Access(int x){
	for(ri y=0;x;y=x,x=f[y]=find(f[y]))
		Splay(x),rc=y,pushup(x);
}
il Make_root(int x){Access(x),Splay(x),pushrev(x);}
it Find_root(int x){
	Access(x),Splay(x);
	while(lc) pushdown(x),x=lc;
	Splay(x);return x;
}
il Split(int x,int y){Make_root(x),Access(y),Splay(y);}
il Delete(int x,int y){if(x) fa[x]=y,Delete(lc,y),Delete(rc,y);}
il Merge(int x,int y){
	if(x==y) return ;
	Make_root(x);
	if(Find_root(y)!=x) return f[x]=y,void();
	Delete(rc,x),rc=0,pushup(x);
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=n;++i) fa[i]=i,sz[i]=1;
	for(ri i=1;i<=m;++i){
		read(u),read(v);
		if(u>v) swap(u,v);
		mp[make_pair(u,v)]=i;
		edge[i]=(Edge){u,v,1};
	}
	while(1){
		read(opt);
		if(opt==-1) break;
		read(x),read(y);
		if(x>y) swap(x,y);
		node[++q]=(Node){opt,x,y};
		if(opt==0) edge[mp[make_pair(x,y)]].vis=0;
	}
	for(ri i=1;i<=m;++i){
		if(!edge[i].vis) continue;
		u=edge[i].u,v=edge[i].v;
		Merge(find(u),find(v));
	}
	for(ri i=q;i;--i){
		opt=node[i].opt,x=node[i].x,y=node[i].y;
		x=find(x),y=find(y);
		if(opt==0) Merge(x,y);
		if(opt==1) Split(x,y),ans[++num]=sz[y]-1;
	}
	for(ri i=num;i;--i)
		print(ans[i]),puts("");
	return 0;
}

维护边权

P4172 [WC2006]水管局长

Solution

显然，题目要求动态维护原图的最小生成树。

我们首先还是考虑将操作离线下来，然后倒序操作。因为加边总比删边好做。

依次考虑加入每一条边，如果两点未连通，那么直接连接。

否则如果两点间的最大权值大于该边权值，那么断掉那条边，在加上该边。

问题就变成了怎么维护最大边权的边。

我们只需要将边拆成点，然后维护最大点权对应的编号即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int N = 2e5+5;
int n,m,q,u,v,d,opt,x,y,num,val[N],ans[N],id[1001][1001];
struct Edge{
	int u,v,dis,vis;
}edge[N];
struct Node{
	int opt,x,y;
}node[N];
int ch[N][2],f[N],mx[N],stk[N];
char rev[N];
#define lc ch[x][0]
#define rc ch[x][1]
inl bool Not_root(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
il pushup(int x){
	mx[x]=x;
	if(lc) if(val[mx[lc]]>val[mx[x]]) mx[x]=mx[lc];
	if(rc) if(val[mx[rc]]>val[mx[x]]) mx[x]=mx[rc];
}
il pushrev(int x){swap(lc,rc),rev[x]^=1;}
il pushdown(int x){
	if(rev[x]){
		if(lc) pushrev(lc);
		if(rc) pushrev(rc);
		rev[x]=0;
	}
}
il Rotate(int x){
	int y=f[x],z=f[y],k=ch[y][1]==x,w=ch[x][!k];
	if(Not_root(y)) ch[z][ch[z][1]==y]=x;
	ch[x][!k]=y,ch[y][k]=w;
	if(w) f[w]=y;
	f[x]=z,f[y]=x,pushup(y);
}
il Splay(int x){
	int y=x,top=0;
	stk[++top]=y;
	while(Not_root(y)) stk[++top]=y=f[y];
	while(top) pushdown(stk[top--]);
	while(Not_root(x)){
		int y=f[x],z=f[y];
		if(Not_root(y)) Rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
		Rotate(x);
	}
	pushup(x);
}
il Access(int x){
	for(ri y=0;x;x=f[y=x])
		Splay(x),rc=y,pushup(x);
}
il Make_root(int x){Access(x),Splay(x),pushrev(x);}
it Find_root(int x){
	Access(x),Splay(x);
	while(lc) pushdown(x),x=lc;
	Splay(x);return x;
}
il Split(int x,int y){Make_root(x),Access(y),Splay(y);}
il Link(int x,int y){Make_root(x),f[x]=y;}
il Cut(int x,int y){Split(x,y),f[x]=ch[y][0]=0,pushup(y);}
il Updata(int x,int y,int dis){
	Make_root(x);
	if(Find_root(y)!=x){
		Link(x,id[x][y]);
		Link(id[x][y],y);
		return ;
	}
	int pos=mx[x];
	if(val[pos]<=dis) return ;
	Cut(edge[pos-n].u,pos);
	Cut(pos,edge[pos-n].v);
	Link(x,id[x][y]);
	Link(id[x][y],y);
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m),read(q);
	for(ri i=1;i<=n;++i) val[i]=-1;
	for(ri i=1;i<=m;++i){
		read(u),read(v),read(d);
		edge[i]=(Edge){u,v,d,1};
		id[u][v]=id[v][u]=i+n,val[i+n]=d;
	}
	for(ri i=1;i<=q;++i){
		read(opt),read(x),read(y);
		node[i]=(Node){opt,x,y};
		if(opt==2) edge[id[x][y]-n].vis=0;
	}
	for(ri i=1;i<=m;++i){
		if(!edge[i].vis) continue;
		Updata(edge[i].u,edge[i].v,edge[i].dis);
	}
	for(ri i=q;i;--i){
		opt=node[i].opt,x=node[i].x,y=node[i].y;
		if(opt==1) Split(x,y),ans[++num]=val[mx[y]];
		if(opt==2) Updata(x,y,edge[id[x][y]-n].dis);
	}
	for(ri i=num;i;--i)
		printf("%d\n",ans[i]);
	return 0;
}

P4234 最小差值生成树

Solution

还是维护生成树，因为要最大值和最小值的差值最小，我们可以考虑枚举最大边或最小边，然后使得另一个尽量靠近。

考虑将边权从小到大排序，然后依次将边加入。

如果还未连通，那么直接连接，否则替换掉其中最小的那一条边。

最小值可以用一个 $multiset$ 来维护，但是也可以用指针维护。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int N = 3e5+5;
int n,m,u,v,d,num,ans=INF,val[N];
struct Edge{
	int u,v,dis;
	bool operator < (const Edge &t) const {
		return dis<t.dis;
	}
}edge[N];
int ch[N][2],f[N],mn[N],stk[N];
char rev[N];
#define lc ch[x][0]
#define rc ch[x][1]
inl bool Not_root(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
il pushup(int x){
	mn[x]=x;
	if(lc) if(val[mn[lc]]<val[mn[x]]) mn[x]=mn[lc];
	if(rc) if(val[mn[rc]]<val[mn[x]]) mn[x]=mn[rc];
}
il pushrev(int x){swap(lc,rc),rev[x]^=1;}
il pushdown(int x){
	if(rev[x]){
		if(lc) pushrev(lc);
		if(rc) pushrev(rc);
		rev[x]=0;
	}
}
il Rotate(int x){
	int y=f[x],z=f[y],k=ch[y][1]==x,w=ch[x][!k];
	if(Not_root(y)) ch[z][ch[z][1]==y]=x;
	ch[x][!k]=y,ch[y][k]=w;
	if(w) f[w]=y;
	f[x]=z,f[y]=x,pushup(y);
}
il Splay(int x){
	int y=x,top=0;
	stk[++top]=y;
	while(Not_root(y)) stk[++top]=y=f[y];
	while(top) pushdown(stk[top--]);
	while(Not_root(x)){
		int y=f[x],z=f[y];
		if(Not_root(y)) Rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
		Rotate(x);
	}
	pushup(x);
}
il Access(int x){
	for(ri y=0;x;x=f[y=x])
		Splay(x),rc=y,pushup(x);
}
il Make_root(int x){Access(x),Splay(x),pushrev(x);}
it Find_root(int x){
	Access(x),Splay(x);
	while(lc) pushdown(x),x=lc;
	Splay(x);return x;
}
il Split(int x,int y){Make_root(x),Access(y),Splay(y);}
il Link(int x,int y){Make_root(x),f[x]=y;}
il Cut(int x,int y){Split(x,y),f[x]=ch[y][0]=0,pushup(y);}
multiset<int> s;
il Updata(int id,int x,int y,int dis){
	Make_root(x),s.insert(dis);
	if(Find_root(y)!=x){
		Link(x,id),Link(id,y),++num;
		return ;
	}
	int pos=mn[x];s.erase(s.find(val[pos]));
	if(val[pos]>=dis) return ;
	Cut(edge[pos-n].u,pos);
	Cut(pos,edge[pos-n].v);
	Link(x,id),Link(id,y);
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=n;++i) val[i]=INF;
	int cnt=0;
	for(ri i=1;i<=m;++i){
		read(u),read(v),read(d);
		if(u==v) continue;
		edge[++cnt]=(Edge){u,v,d};
	}
	sort(edge+1,edge+1+cnt),m=cnt;
	for(ri i=1;i<=m;++i) val[i+n]=edge[i].dis;
	for(ri i=1;i<=m;++i){
		Updata(i+n,edge[i].u,edge[i].v,edge[i].dis);
		if(num==n-1) ans=min(ans,edge[i].dis-*s.begin());
	}
	print(ans);
	return 0;
}

维护子树信息

P4219 [BJOI2014]大融合

Solution

利用 $LCT$ 维护子树信息模板题。

用 $LCT$ 维护子树和一般的写法有一些不同。

  1. 额外维护了一个数组 $s1$ 表示虚子树的信息，在 $pushup$ 时也要加上。
  2. 在 $Access$ 时，由于改变了子树的虚实，需要及时更改。
  3. 在 $Link$ 时，会给 $y$ 多一条虚边，要及时加上，但是直接加会使 $y$ 的父节点都要加，可以先 $Make_root(y)$ 再改。

然后答案就是 $Split(x,y)$ 后， $x$ 的虚子树大小加 $1$ 乘上 $y$ 的虚子树大小加 $1$ 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int N = 1e5+5;
int n,m,u,v;
int ch[N][2],f[N],sz[N],s1[N],stk[N];
char rev[N],opt[2];
#define lc ch[x][0]
#define rc ch[x][1]
inl bool Not_root(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
il pushup(int x){sz[x]=sz[lc]+sz[rc]+s1[x]+1;}
il pushrev(int x){swap(lc,rc),rev[x]^=1;}
il pushdown(int x){
	if(rev[x]){
		if(lc) pushrev(lc);
		if(rc) pushrev(rc);
		rev[x]=0;
	}
}
il Rotate(int x){
	int y=f[x],z=f[y],k=ch[y][1]==x,w=ch[x][!k];
	if(Not_root(y)) ch[z][ch[z][1]==y]=x;
	ch[x][!k]=y,ch[y][k]=w;
	if(w) f[w]=y;
	f[x]=z,f[y]=x,pushup(y);
}
il Splay(int x){
	int y=x,top=0;
	stk[++top]=y;
	while(Not_root(y)) stk[++top]=y=f[y];
	while(top) pushdown(stk[top--]);
	while(Not_root(x)){
		int y=f[x],z=f[y];
		if(Not_root(y)) Rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
		Rotate(x);
	}
	pushup(x);
}
il Access(int x){
	for(ri y=0;x;x=f[y=x]){
		Splay(x);
		s1[x]+=sz[rc];
		s1[x]-=sz[rc=y];
		pushup(x);
	}
}
il Make_root(int x){Access(x),Splay(x),pushrev(x);}
it Find_root(int x){
	Access(x),Splay(x);
	while(lc) pushdown(x),x=lc;
	Splay(x);return x;
}
il Split(int x,int y){Make_root(x),Access(y),Splay(y);}
il Link(int x,int y){
	Make_root(x),Make_root(y);
	s1[f[x]=y]+=sz[x],pushup(y);
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=m;++i){
		scanf("%s",opt),read(u),read(v);
		if(opt[0]=='Q'){
			Split(u,v);
			print(1ll*(s1[u]+1)*(s1[v]+1)),puts("");
		}
		if(opt[0]=='A') Link(u,v);
	}
	return 0;
}

我们的 CPU 遭到攻击

Solution

套路题？

我们分别维护以下变量：

  1. $lans$ ：一个 $splay$ 子树中的所有黑点到其子树中深度最浅的点的距离和。
  2. $rans$ ：一个 $splay$ 子树中的所有黑点到其子树中深度最深的点的距离和。
  3. $ians$ ：一个点的所有虚儿子所在的 $splay$ 中的所有黑点到其对应的虚儿子的距离。
  4. $ds$ ：一个 $splay$ 中的黑点个数。
  5. $ids$ ：一个点的所有虚儿子所在的 $splay$ 中的黑点个数。

那么询问的答案就是 $x$ 为根时， $lans_x$ 的值。

因为有翻转操作，所以最深会变为最浅，最浅会变为最深，直接交换 $lans_x,rans_x$ 即可。

注意 $pushup$ 时，由于 $x$ 和 $lc$ 所在的 $splay$ 子树中的黑点，还没有走到当前的最深/最浅，我们需要将这一段加上。

同时注意在 $Access$ 和 $Link$ 时更新 $ians,ids$ 即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int N = 4e5+5;
int n,m,q,u,v,d,num,val[N];
int ch[N][2],f[N],ds[N],ids[N],stk[N];
ll lans[N],rans[N],ians[N],s[N];
char rev[N],col[N],opt[2];
#define lc ch[x][0]
#define rc ch[x][1]
inl bool Not_root(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
il pushup(int x){
	s[x]=s[lc]+s[rc]+val[x];
	ds[x]=ds[lc]+ds[rc]+ids[x]+col[x];
	lans[x]=ians[x]+lans[lc]+lans[rc]+(ids[x]+ds[rc]+col[x])*(val[x]+s[lc]);
	rans[x]=ians[x]+rans[lc]+rans[rc]+(ids[x]+ds[lc]+col[x])*(val[x]+s[rc]);
}
il pushrev(int x){swap(lans[x],rans[x]),swap(lc,rc),rev[x]^=1;}
il pushdown(int x){
	if(rev[x]){
		if(lc) pushrev(lc);
		if(rc) pushrev(rc);
		rev[x]=0;
	}
}
il Rotate(int x){
	int y=f[x],z=f[y],k=ch[y][1]==x,w=ch[x][!k];
	if(Not_root(y)) ch[z][ch[z][1]==y]=x;
	ch[x][!k]=y,ch[y][k]=w;
	if(w) f[w]=y;
	f[x]=z,f[y]=x,pushup(y);
}
il Splay(int x){
	int y=x,top=0;
	stk[++top]=y;
	while(Not_root(y)) stk[++top]=y=f[y];
	while(top) pushdown(stk[top--]);
	while(Not_root(x)){
		int y=f[x],z=f[y];
		if(Not_root(y)) Rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
		Rotate(x);
	}
	pushup(x);
}
il Access(int x){
	for(ri y=0;x;x=f[y=x]){
		Splay(x);
		ids[x]+=ds[rc]-ds[y];
		ians[x]+=lans[rc]-lans[y];
		rc=y,pushup(x);
	}
}
il Make_root(int x){Access(x),Splay(x),pushrev(x);}
il Split(int x,int y){Make_root(x),Access(y),Splay(y);}
il Link(int x,int y){
	Make_root(x),Make_root(y);
	f[x]=y,ids[y]+=ds[x],ians[y]+=lans[x];
	pushup(y);
}
il Cut(int x,int y){Split(x,y),f[x]=ch[y][0]=0,pushup(y);}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m),read(q),num=n;
	for(ri i=1;i<=m;++i){
		read(u),read(v),read(d);
		val[++num]=d;
		Link(u,num),Link(v,num);
	}
	for(ri i=1;i<=q;++i){
		scanf("%s",opt);
		if(opt[0]=='L'){
			read(u),read(v),read(d);
			val[++num]=d;
			Link(u,num),Link(v,num);
		}
		if(opt[0]=='C'){
			read(u),read(v),Split(u,v);
			int p=ch[v][0];
			Cut(u,p),Cut(v,p);
		}
		if(opt[0]=='F')
			read(u),Access(u),Splay(u),col[u]^=1,pushup(u);
		if(opt[0]=='Q')
			read(u),Make_root(u),print(lans[u]),puts("");
	}
	return 0;
}

P4299 首都

Solution

动态维护树的重心。

有两种做法：

启发式合并

每次将小的合并到大的上面去，由于重心的性质，每次重心要么不变，要么向新加的叶子处移动一格，用 $LCT$ 维护即可。

时间复杂度： $O(n\log^2 n)$ 。

$Splay$ 树上二分

树的重心有一个很好的性质：两颗树合并后，新的重心一定在原来两棵树的重心连线上。

所以我们可以将原来的两个重心 $Split$ 出来，然后在上面二分。

结束条件是左右子树的大小均不超过总大小的一半。

由于可能有两个重心，所以需要找完，还有每次记得 $pushdown$ 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int N = 1e5+5;
int n,m,u,v,x,y,sum,fa[N];
int ch[N][2],f[N],s[N],si[N],stk[N];
char rev[N],opt[10];
#define lc ch[x][0]
#define rc ch[x][1]
inl bool Not_root(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
il pushup(int x){s[x]=s[lc]+s[rc]+si[x]+1;}
il pushrev(int x){swap(lc,rc),rev[x]^=1;}
il pushdown(int x){
	if(rev[x]){
		if(lc) pushrev(lc);
		if(rc) pushrev(rc);
		rev[x]=0;
	}
}
il Rotate(int x){
	int y=f[x],z=f[y],k=ch[y][1]==x,w=ch[x][!k];
	if(Not_root(y)) ch[z][ch[z][1]==y]=x;
	ch[x][!k]=y,ch[y][k]=w;
	if(w) f[w]=y;
	f[x]=z,f[y]=x,pushup(y);
}
il Splay(int x){
	int y=x,top=0;
	stk[++top]=y;
	while(Not_root(y)) stk[++top]=y=f[y];
	while(top) pushdown(stk[top--]);
	while(Not_root(x)){
		int y=f[x],z=f[y];
		if(Not_root(y)) Rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
		Rotate(x);
	}
	pushup(x);
}
il Access(int x){
	for(ri y=0;x;x=f[y=x]){
		Splay(x);
		si[x]+=s[rc],si[x]-=s[rc=y];
		pushup(x);
	}
}
il Make_root(int x){Access(x),Splay(x),pushrev(x);}
il Split(int x,int y){Make_root(x),Access(y),Splay(y);}
il Link(int x,int y){
	Make_root(x),Make_root(y);
	f[x]=y,si[y]+=s[x],pushup(y);
}
it find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
it Updata(int x){
	int l,r,odd=s[x]&1,sum=s[x]>>1,lsum=0,rsum=0,res=INF,nwl,nwr;
	while(x){
		pushdown(x);
		nwl=s[l=lc]+lsum,nwr=s[r=rc]+rsum;
		if(nwl<=sum&&nwr<=sum){
			if(odd){res=x;break;}
			if(res>x) res=x;
		}
		if(nwl<nwr) lsum+=s[l]+si[x]+1,x=r;
		else rsum+=s[r]+si[x]+1,x=l;
	}
	Splay(res);return res;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=n;++i)
		fa[i]=i,sum^=i;
	for(ri i=1;i<=m;++i){
		scanf("%s",opt);
		if(opt[0]=='X') print(sum),puts("");
		if(opt[0]=='Q') read(x),print(find(x)),puts("");
		if(opt[0]=='A'){
			read(x),read(y),Link(x,y);
			x=find(x),y=find(y),sum^=x^y;
			Split(x,y);int z=Updata(y);
			sum^=z,fa[x]=fa[y]=fa[z]=z;
		}
	}
	return 0;
}