记录编号	608772	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	4185.通讯网络	最终得分	100
用户昵称	梦那边的美好TE	是否通过	通过
代码语言	C++	运行时间	27.585 s
提交时间	2025-10-29 07:28:05	内存使用	130.09 MiB

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
const int MAXSIZE=(1<<20);
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2)?EOF:*p1++)
inline int read(){
	int x=0,f=1;char ch=gc();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
	while(isdigit(ch))x=(x<<3)+(x<<1)+ch-48,ch=gc();
	return x*f;
}
const int N=1e6+10;
const int M=2e6+10;
typedef long long ll;
set<int>G[N],vec[N];
int o,n,m,fa[N],idx;
ll now,del[M];
struct node{
	int u,fat;
	set<int>::iterator hd;
};
ll link(int u,int v){
	G[u].insert(v);
	G[v].insert(u);
	int a=fa[u],b=fa[v];
	ll cnt=vec[a].size()*vec[b].size();
	if(vec[a].size()>vec[b].size()){
		swap(u,v),swap(a,b);
	}
	for(auto p:vec[a]){
		vec[b].insert(p);
		fa[p]=b;
	}
	return cnt;
}
ll cut(int u,int v){
	G[u].erase(v),G[v].erase(u);
	vector<int>V[2];
	queue<node>q[2];
	V[0].push_back(u);
	V[1].push_back(v);
	if(G[u].size())q[0].push(node{u,0,G[u].begin()});
	if(G[v].size())q[1].push(node{v,0,G[v].begin()});
	int nxt=0;long long cnt;
	while(q[0].size()&&q[1].size()){
		int o=(V[0].size()>V[1].size());
		node t=q[o].front();q[o].pop();
		if(t.hd==G[t.u].end())continue;
		if((nxt=*t.hd)!=t.fat){
			V[o].push_back(nxt);
			q[o].push(node{nxt,t.u,G[nxt].begin()});
		}
		t.hd++;
        if(t.hd!=G[t.u].end())q[o].push(t);
	}
	if(!q[1].size()&&(q[0].size()||V[1].size()<V[0].size())){
		swap(u,v),swap(V[0],V[1]);
	}
	cnt=V[0].size()*(vec[fa[u]].size()-V[0].size());
	assert(V[0].size()*2<=vec[fa[u]].size());
	++idx;
	for(auto p:V[0]){
		fa[p]=idx;
		vec[idx].insert(p);
		vec[fa[v]].erase(p);
	}
	return cnt;
}
int main(){ 
	freopen("communication.in","r",stdin);
	freopen("communication.out","w",stdout); 
	o=read();
	n=read(),m=read();
	int op,x,y,t;ll lst=0;
	for(int i=1;i<=n;i++){
		vec[i].insert(i);
		fa[i]=i; 
	}
	idx=n;
	for(int i=n+1;i<=2*n;i++)fa[i]=i;
	for(int T=1;T<=m;T++){
		op=read();
		if(op==1){
			x=read(),y=read(); 
			if(o)x^=lst,y^=lst;
			now+=link(x,y);
		}
		if(op==2){
			x=read(),y=read();
			if(o)x^=lst,y^=lst;
			del[T]=cut(x,y);
		}
		del[T]+=del[T-1];
		if(op==3){
			t=read();
			if(o)t^=lst;
			lst=now-del[T-t];
			cout<<lst<<'\n';
		}
	}
	return 0;
}