526互联

AtCoder Regular Contest 141 E Sliding Edge on Torus

发布时间 2023-06-20 11:44:49作者: zltzlt

洛谷传送门

AtCoder 传送门

\((i, j) \to (i - j, j)\)，那么我们每次连边 \((u_i, k)\) 和 \((v_i, k + p_i)\)。

考虑给每一行设置一个偏移量 \(b_i\)，\((i, j) \to (i, j + h_i)\)，使得连边时，如果 \(u_i\) 和 \(v_i\) 行的任意两点都不在一个集合，那么 \(p_i = 0\)。这样我们就可以做一维的情况了，维护集合的 \(\gcd\) 即可。

而这个 \(b_i\) 一定有解，连边 \((u_i, v_i, p_i)\) 表示 \(b_{u_i} - b_{v_i} = p_i\)，不难发现这样构造的是一个森林。一遍 dfs 求解即可。

code 
// Problem: E - Sliding Edge on Torus
// Contest: AtCoder - AtCoder Regular Contest 141
// URL: https://atcoder.jp/contests/arc141/tasks/arc141_e
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;

int n, m, head[maxn], len, fa[maxn], a[maxn], b[maxn], deg[maxn];
bool vis[maxn];

struct edge {
	int to, dis, next;
} edges[maxn << 1];

struct node {
	int u, v, d;
	node(int a = 0, int b = 0, int c = 0) : u(a), v(b), d(c) {}
} qq[maxn];

inline void add_edge(int u, int v, int d) {
	edges[++len].to = v;
	edges[len].dis = d;
	edges[len].next = head[u];
	head[u] = len;
}

int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void dfs(int u) {
	vis[u] = 1;
	for (int i = head[u]; i; i = edges[i].next) {
		int v = edges[i].to, d = edges[i].dis;
		if (vis[v]) {
			continue;
		}
		b[v] = (b[u] - d + n) % n;
		dfs(v);
	}
}

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i) {
		fa[i] = i;
	}
	for (int i = 1, a, b, c, d; i <= m; ++i) {
		scanf("%d%d%d%d", &a, &b, &c, &d);
		a = (a - b + n) % n;
		c = (c - d + n) % n;
		b = (d - b + n) % n;
		qq[i] = node(a, c, b);
		int x = find(a), y = find(c);
		if (x != y) {
			fa[x] = y;
			add_edge(a, c, b);
			add_edge(c, a, (n - b) % n);
		}
	}
	for (int i = 0; i < n; ++i) {
		if (!vis[i]) {
			dfs(i);
		}
	}
	ll ans = 1LL * n * n;
	for (int i = 0; i < n; ++i) {
		fa[i] = i;
		a[i] = n;
	}
	for (int i = 1; i <= m; ++i) {
		int u = qq[i].u, v = qq[i].v, d = (qq[i].d + b[qq[i].v] - b[qq[i].u] + n) % n;
		int x = find(u), y = find(v);
		if (x != y) {
			ans -= a[x];
			ans -= a[y];
			fa[x] = y;
			a[y] = __gcd(a[x], a[y]);
			ans += a[y];
		} else {
			ans -= a[x];
			a[x] = __gcd(a[x], d);
			ans += a[x];
		}
		printf("%lld\n", ans);
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}