[eJOI 2024] 奶酪交易 / Cheese

前言：

译者的语文成绩不怎么样啊。

解题思路：

假设农夫 \(i\) 所拥有的奶酪价值为 \(p_{i}\)。

稍微细想一下 \(i\) 和 \(j\) 交易这件事，因为钱的面值只有 \(2\) 的次幂，所以 \(j\) 找 \(i\) 的钱的总面值一定是 \(B\) 的倍数，发现它实际上是想告诉我们：

\[p_{j}-p_{i}=A-k \times B \quad k \in \mathbb{Z} \]

\[p_{j}-p_{i} \equiv A \pmod{B} \]

在细想一下又能发现，我们不仅仅只知道 \(p_{j}-p_{i}\) 模 \(B\) 的值，小于 \(B\) 的值我们也能知道。所以一次交易相当于告诉我们 \(p_{j}-p_{i}\) 模所有小于 \(B\) 的面值的差值。

注意到 \(B\) 的面值不会大于 \(2^{15}\)，所以我们直接开 \(16\) 个带权并查集，第 \(i\) 个并查集中记录 \(fa_{x}\) 表示 \(x\) 的父亲，\(val_{x}\) 表示 \(p_{x}\) 在模 \(2^i\) 的意义下减 \(p_{fa_{x}}\) 的差值。

每次交易只要查询 \(i\) 和 \(j\) 是否在并查集内是否有连边，差值是否正确即可。

\(x\) 所在的并查集和 \(y\) 所在的并查集合并的时候，我们知道的是 \(p_{x}\) 和 \(p_{y}\) 之间的差 \(k\)，那么这两个并查集的根节点之间的边权应为 \(k-val[x]+val[y]\)。（这部分请根据具体实现自行推断）

同时注意路径压缩时，\(x\) 的父节点变了，\(val_{x}\) 的值也要变。

\(B=-1\) 其实是容易的，只要将 \(B\) 当作一个足够大的值做就行了。

代码实现：

#include<bits/stdc++.h>
#define endl '\n'
#define LL long long
using namespace std;
const int N = 5e5 + 10;
int n, m;
struct DSU{int fa[N];LL val[N], mod;int find(int x){if(fa[x] == x) return x;int fat = find(fa[x]);val[x] = (val[x] + val[fa[x]]);return fa[x] = fat;}bool check(int x, int y, LL k){int fatx = find(x), faty = find(y);if(fatx != faty) return 1;return (((val[x] - val[y]) % mod + mod) % mod == k);}void merge(int x, int y, LL k){int fatx = find(x), faty = find(y);if(fatx == faty) return;fa[fatx] = faty;val[fatx] = k + val[y] - val[x];}
}T[17];
signed main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> m;for(int j = 0; j <= 15; j++) T[j].mod = (1 << j);T[16].mod = 0x3f3f3f3f3f3f3f3f;for(int i = 1; i <= n; i++) for(int j = 0; j <= 16; j++) T[j].fa[i] = i;for(int i = 1; i <= m; i++){LL x, y, val, B;cin >> x >> y >> val >> B;if(B != -1){int k = log2(B);for(int i = k; i >= 0; i--) if(!T[i].check(x, y, val & (T[i].mod - 1))) goto failed;for(int i = k; i >= 0; i--) T[i].merge(x, y, val & (T[i].mod - 1));}else{int k = 15;if(!T[16].check(x, y, val)) goto failed;for(int i = k; i >= 0; i--) if(!T[i].check(x, y, val & (T[i].mod - 1))) goto failed;for(int i = k; i >= 0; i--) T[i].merge(x, y, val & (T[i].mod - 1));T[16].merge(x, y, val);}cout << 1 << endl; continue;failed: cout << 0 << endl;}return 0;
}