https://www.luogu.com.cn/record/112472035

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second 
#define deb(var) cerr << #var << '=' << var << "; "
#define ll long long
int n, m, a[200010]; 
struct Ques {
	int op, l, r, a, x, y;
} q[200010];
vector<int> sub[200010];
int fa[200010], siz[200010]; ll val[200010];
int find(int u) {
	if (fa[u] == u) return u; return fa[u] = find(fa[u]);
}
int qry(int c, int x) {
	return upper_bound(sub[c].begin(), sub[c].end(), x) - sub[c].begin() - 1;
}
ll c[200010];
inline char nc()
{
	static char buf[1000000],*l,*r;
	return l==r&&(r=(l=buf)+fread(buf,1,1000000,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
inline void read(long long&x)
{
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
signed main() {
	read(n), read(m);
	for (int i = 1; i <= m; i++) {
		read(q[i].op);
		if (q[i].op == 1) read(q[i].x), read(q[i].y);
		else if (q[i].op == 2) read(q[i].l), read(q[i].r), read(q[i].a); else read(q[i].x);
	}
	for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1, sub[i].pb(i);
	int len = 800;
	for (int l = 1; l <= m; l += len) {
		int r = min(m, l + len - 1);
		for (int i = l; i <= r; i++) {
			if (q[i].op == 1) {
				int fx = find(q[i].x), fy = find(q[i].y);
				if (fx != fy) {
					if (siz[fx] < siz[fy]) swap(fx, fy), swap(q[i].x, q[i].y);
					fa[fy] = fx;
					for (int j = 0; j < sub[fy].size(); j++) 
						sub[fx].pb(sub[fy][j]); 
					sub[fy].clear(); sort(sub[fx].begin(), sub[fx].end()); val[fx] += val[fy];
				}
			} else if (q[i].op == 3) {
				int u = q[i].x, fa = find(u); ll ans = val[fa];
				for (int j = l; j <= i; j++) {
					if (q[j].op == 2) {
						ans += q[j].a * (ll)(qry(fa, q[j].r) - qry(fa, q[j].l - 1)); 
					}
				}
				cout << ans << "\n";
			}
		}
		memset(c, 0, sizeof c);
		for (int i = l; i <= r; i++) {
			if (q[i].op == 2) c[q[i].l] += q[i].a, c[q[i].r + 1] -= q[i].a;
		}
		for (int i = 1; i <= n; i++) c[i] += c[i - 1];
		for (int i = 1; i <= n; i++) {
			if (fa[i] == i) {
				for (int j = 0; j < sub[i].size(); j++) val[i] += c[sub[i][j]];
			}
		}
	}
	return 0;
}