#include<algorithm>
#include<cstdio>
#include<stack>
#define INL inline
const int N=1e6+5;

int n,m,ans,tot;

INL int read()
{
	int x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')w=-1,ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-48,ch=getchar();
	return x*w;
}

struct ReyLCT
{
	int fa[N],ch[N][2],val[N],sum[N],clear[N],rev[N];
/* basic operations of a Data Structure */	
	INL void UPDATE(int p){sum[p]=sum[ch[p][0]]+sum[ch[p][1]]+val[p];}
	INL void PD(int p)
	{
		if(rev[p]){rev[p]=0,rev[ch[p][0]]^=1,rev[ch[p][1]]^=1;std::swap(ch[p][0],ch[p][1]);}
		if(clear[p])
		{
			clear[p]=0;clear[ch[p][0]]=clear[ch[p][1]]=1;
			val[ch[p][0]]=val[ch[p][1]]=sum[ch[p][0]]=sum[ch[p][1]]=0;
		}
	}
/* some implemental functions for vertices judgement*/	
	INL bool ISroot(int p){return ch[fa[p]][0]!=p&&ch[fa[p]][1]!=p;}
	INL int Get_pos(int p){return (int)(ch[fa[p]][1]==p);}
/* Splay for Link-Cut-Tree */
	INL void Rotate(int x)
	{
		int y=fa[x],z=fa[y];
		int L=Get_pos(x),R=L^1;
		if(!ISroot(y))ch[z][Get_pos(y)]=x;
		fa[x]=z;fa[y]=x;fa[ch[x][R]]=y;ch[y][L]=ch[x][R];ch[x][R]=y;
		UPDATE(y);UPDATE(x);
	}
	INL void Splay(int p)
	{
		std::stack <int> stk;stk.push(p);
		for(int i=p;!ISroot(i);i=fa[i])stk.push(fa[i]);
		while(!stk.empty())PD(stk.top()),stk.pop();
		while(!ISroot(p))
		{
			int f=fa[p];
			if(!ISroot(f))Get_pos(f)^Get_pos(p)?Rotate(p):Rotate(f);
			Rotate(p);
		}
	}
/* Link-Cut-Tree */	
	INL void Access(int p){for(int i=0;p;i=p,p=fa[p])Splay(p),ch[p][1]=i,UPDATE(p);}
	INL void Makeroot(int p){Access(p);Splay(p);rev[p]^=1;}
	INL int Findroot(int p){Access(p);Splay(p);while(ch[p][0])p=ch[p][0];return p;}
	INL void Split(int p,int q){Makeroot(p);Access(q);Splay(q);}
	INL void Cut(int p,int q){Split(p,q);if(ch[p][1]==0&&fa[p]==q&&ch[q][0]==p)ch[q][0]=0,fa[p]=0;}
	INL void Link(int p,int q){Makeroot(p);fa[p]=q;}
	INL bool ISconnected(int p,int q){return Findroot(p)==Findroot(q);}
/* Section for P5622 */
	INL void dfs_con(int x,int f)
	{
		fa[x]=f;PD(x);
		if(ch[x][0])dfs_con(ch[x][0],f);
		if(ch[x][1])dfs_con(ch[x][1],f);
		ch[x][0]=ch[x][1]=0;
		UPDATE(x);
	}
}LCT;

INL void Decode(int &x,int key)
{
	x^=key%n;
	if(x>n)x%=n;
	if(!x)x=1;
}

int main()
{
	n=read(),m=read();
	while(m--)
	{
		int opt=read(),x=read(),y=read();
		Decode(x,ans);Decode(y,ans);
		if(opt==1)
		{
			if(x==y)continue;
			if(!LCT.ISconnected(x,y))LCT.Link(x,y);
			else {LCT.Split(x,y);++tot;LCT.dfs_con(y,n+tot);}
		}
		if(opt==2)
		{
			LCT.Splay(x);LCT.val[x]+=y;LCT.UPDATE(x);
		}
		if(opt==3)
		{
			if(!LCT.ISconnected(x,y))ans=0;
			else
			{
				LCT.Split(x,y);ans=LCT.sum[y];
				LCT.sum[y]=LCT.val[y]=0;
				LCT.clear[y]=1;
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

单纯想问一下，LCT 这样全部封装进结构体会很慢么。。。

7.5s -> 1.5s ，这 O2 也太劲了吧 qwq