带权并查集

Weighted Disjoint-set(带权并查集)

eg带权并查集

给你个变量，一开始不知道这些数是多少。

你要执行次操作。

• 1 l r x，给你一条线索，表示，如果与已知条件矛盾，那么忽略这次操作。
• 2 l r回答，如果现在的线索无法推出答案，那么忽略这次操作。

强制在线(读一个操作一个)：

有一个变量，一开始，每次未被忽略的查询操作之后，会变成答案的绝对值，也就是。每次操作输入的是加密后的实际上的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 201000;
int n,q,fa[N];
ll w[N];

int find(int x)
{
	if(x==fa[x])return x;
	int p = fa[x];
	find(p);//先把fa[x]做一个路径压缩，假设现在的fa[p] =  q
	/*
		w[x] = a[x]-a[p]
		fa[p] = q , w[p]:a[p]-a[q]
		fa[x] = p , w[x]:a[x]-a[p]
		a[x] - a[p] + a[p] - a[q] = a[x]+a[p]
	*/
	w[x] = w[x]+w[p];
	return fa[x] = fa[p];
}

int main()
{
	cin>>n>>q;
	//w[i] = a[i]-a[fa[i]];
	for(int i = 1;i<=n;i++)fa[i] = i,w[i] = 0;
	ll t = 0;
	for(int i = 0;i<q;i++)
	{	
		int op,l,r;
		cin>>op>>l>>r;
		l = (l+t)%n + 1;
		r = (r+t)%n + 1;
		if(op==2)
		{
			if(find(l)!=find(r))continue;
			else cout<<w[l]-w[r]<<endl;
			t = abs(w[l]-w[r]);
		}
		else if(op==1)
		{
			int x;
			cin>>x;
			if(find(l)==find(r))continue;
			/*
				w[fa[l]] = a[fa[l]]-a[fa[r]];
				a[l]-a[r] = x;
				w[l] = a[l]-a[fa[l]],w[r] = a[r]-a[fa[r]];
				a[l] - w[l] = a[fa[l]],a[r]-w[r] = a[fa[r]]
				w[fa[l]] = a[l]-w[l]-(a[r]-w[r])
			*/
			//先改权值再变父亲
			w[fa[l]] = x-w[l]+w[r];
			fa[fa[l]] = fa[r];
		}
	}
	return 0;
}