带权并查集

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define x first
#define y second
#define int long long 
const int N=1e6+10,mod=998244353;

int f[N],w[N];//w[i]表示i这个点比根节点的值大多少 

int find(int x){
	if(f[x]==x) return x;
	int p=f[x];
	find(p);
	/*
	更新前:f[x]=p,w[x]=a[x]-a[p]
	更新前:f[p]=q, w[p]=a[p]-a[q]
	更新后:f[x]=q, w[x]=a[x]-a[q]
	w[x](更新前)+w[p]=a[x]-a[p]+a[p]-a[q]=a[x]-a[q]=w[x](更新后)
	*/
	w[x]+=w[p];
	return f[x]=f[p];
}

void slove(){
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		f[i]=i;
		w[i]=0;
	}
	int t=0;
	while(q--){
		int ty,l,r;
		cin>>ty>>l>>r;
		l=(l+t)%n+1;
		r=(r+t)%n+1;
		if(ty==2){
			if(find(l)!=find(r))continue;
			cout<<w[l]-w[r]<<endl;
			t=abs(w[l]-w[r]);
		}else {
			if(find(l)==find(r)) continue;
			//只要统计根节点之间的关系即可,后续的更新会在find中完成 
			/*
			w[f[l]]=a[f[l]]-a[f[r]];
			a[l]-a[r]=x;
			a[l]-w[l]-(a[r]-w[r])=a[f[l]]-a[f[r]]
			*/
			w[f[l]]=x-w[l]+w[r];
			f[f[l]]=f[r];//l并为r的儿子节点
		}
	} 
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	int T=1;
	while(T--) slove();
}