带权并查集

带权并查集

const int N = 2e5 + 10;
int n, q;
int f[N];
long long w[N];
int find(int x) {
    if (f[x] == x)
        return x;
    int p = f[x];
    find(p);
    w[x] = w[x] + w[p];
    return f[x] = f[p];
}
signed main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        f[i] = i;
        w[i] = 0;
    }
    long long t = 0;
    while (q--) {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        l = (l + t) % n + 1;
        r = (r + t) % n + 1;
        if (op == 1) {//a[l]-a[r]=x;
            int x;
            scanf("%d", &x);
            if (find(l) == find(r))
                continue;
            w[f[l]] = x - w[l] + w[r];
            f[f[l]] = f[r];
        }
        else {
            if (find(l) != find(r))
                continue;
            printf("%lld\n", w[l] - w[r]);
            t = abs(w[l] - w[r]);
        }
    }
    return 0;
}