这题为啥能上 3000，我这种废物都能一眼看出来做法...
首先发现可以将点根据 \(x - y\) 的值分成 \(n\) 组，第 \(x\) 组的第 \(i\) 个点为 \((i, i + x)\)，这样每次连边的时候肯定是两组之间的所有点进行连边。
考虑将两组点连在一起之后，相当于将两组 \(n\) 个点合并成了一组 \(n\) 个点，第一组中的第 \(i\) 个点与第二组中的第 \(j\) 个点相连。这样看起来很烦，所以我们可以维护每组的一个偏移量，使得它们能够第 \(i\) 个点与第 \(i\) 个点相连。直接并查集启发式合并维护即可。
然后考虑一个连通块中连第二条边，那么显然这 \(n\) 个点会被这条边划分成若干个连通块，假如当前每个连通块中每个点距离为 \(d\)，新的边跨过的点数量为 \(c\)，那么连完之后得到的新连通块的每个点距离就是 \(\gcd(d, c)\)。这个距离同时也是连通块的个数。
那么直接并查集维护即可。注意当两组合并的时候，两组的连通块距离也可能不同，所以合并之后新的距离是原来两个距离的 \(\gcd\)。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, q;
int norm(int x) {
return (x % n + n) % n;
}
int siz[MAXN], fa[MAXN], off[MAXN], f[MAXN];
vector<int> pts[MAXN];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 0; i < n; i++) {
siz[i] = 1, f[i] = n, fa[i] = i;
pts[i].push_back(i);
}
long long ans = 1ll * n * n;
for (int i = 1; i <= q; i++) {
int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
int x = norm(a - b), y = norm(c - d), dif = norm((a - off[x]) - (c - off[y]));
if (find(x) != find(y)) {
x = find(x), y = find(y);
if (siz[x] > siz[y]) swap(x, y), dif = norm(-dif);
fa[x] = y;
siz[y] += siz[x];
for (int p : pts[x]) {
off[p] = norm(off[p] + dif);
pts[y].push_back(p);
}
ans -= f[x] + f[y];
f[y] = __gcd(f[x], f[y]);
ans += f[y];
} else {
int dd = norm((a - off[x]) - (c - off[y]));
int u = find(x);
ans -= f[u];
f[u] = __gcd(f[u], dd);
ans += f[u];
}
printf("%lld\n", ans);
}
return 0;
}