每个人都有三个地址

旧剧院只认门牌，不认故事。

后台有一台很固执的机器。两个人的牌子相同，机器就说他们属于同一组；牌子不同，机器拒绝继续听。

导演每天拿着剧本来，机器每天只回答“同组”或者“不同组”。

一开始，问题很小。两个演员能不能分到同一个休息室。

后来剧本长出了别的要求。甲必须和乙分开。

甲演的角色要压住乙。

乙又要压住丙。丙绕一圈，回头压住甲。

机器仍然只会看牌子。

道具师没有重写机器。他给每个演员多印了几张牌，分别写着“我是谁”“我站在对面”“我压着谁”。

每条新规都被改写成两张或三张牌应该相同。

排练当晚，导演拿着三张牌走进后台。灯一亮，机器终于听懂了剧本。

简化题面

┌─ [P1525] 关押罪犯 / [P2024] 食物链
├─ 平台: 洛谷
├─ P1525: 给出带仇恨值的罪犯关系，求二分分组能承受的最大冲突阈值。
├─ P2024: 给出同类与捕食陈述，统计其中自相矛盾的陈述数量。
├─ 输入: 两题均为关系操作，但参数格式和输出含义不同。
├─ 数据范围: 对象数与操作数较大，需要近乎常数的合并与查询。
├─ 关键限制: 关系复合后仍落在有限个角色类型中。
└─ 完整题面: https://www.luogu.com.cn/problem/P1525；https://www.luogu.com.cn/problem/P2024

机器只会认同组

并查集的原始接口只有两件事：合并两个集合，查询两个对象是否连通。

P1525 的对立关系可以借一张影子牌表达。给对象 x 两个位置：

x      ：x 所在的一侧
x + n  ：x 的另一侧

要求 x 与 y 分开，就把 x 接到 y 的影子，把 x 的影子接到 y：

union(x, y + n);
union(x + n, y);

某次加入关系后，若 find(x)==find(y)，先前的高优先级约束已经把两人推到同一侧，当前关系无法再成立。按仇恨从大到小加入，第一次撞上的权值就是阈值。

两倍空间只是一种结果。第二份节点必须有清楚语义，每条关系必须能改写成连通约束。

三张牌围成一圈

P2024 的关系有三个角色：同类、被我捕食的类、捕食我的类。

每个对象 x 拥有三个位置：

x        ：与 x 同类
x + n    ：x 捕食的类
x + 2*n  ：捕食 x 的类

“x 吃 y”会同时锁定三条关系：

union(x + n,   y);
union(x + 2*n, y + n);
union(x,       y + 2*n);

第一条最容易想到。后两条来自角色循环，少一条，下一次关系复合就会留下缝。

扩展域的关键动作是先命名角色，再沿关系走一圈。数组开几倍，等角色空间定下来才有意义。

牌面增加，户口也要增加

三倍域第一次落码时，初始化仍停在：

for (int i = 1; i <= n; ++i) fa[i] = i;

额外两份地址落进全局数组的零值里。纸面上有三座后台，内存里却都挤在根 0 门下。

改成初始化到 3*n 后，关系才按预期分开。

这是边界错误，也是一种模型验收。表示空间扩展以后，初始化、清空、访问范围、数组容量必须一起扩展。

什么时候别再扩地址

扩展域适合有限角色和稳定复合。二分对立有两个角色，食物链是模三循环。

关系带任意数值，或复合后不断产生新类型，有限份影子牌很快用完。带权并查集、图搜索或其他结构会更合适。

写代码前先问四件事：

每一份地址代表哪个角色？
两条关系连续发生，第三条关系怎样推出？
新事实需要同时合并哪些角色？
哪种连通状态代表矛盾？

四个答案写在纸上以后，2*n 或 3*n 只是数组长度。

排练散场。后台机器仍然只说“同组”。

导演把三张牌收回剧本夹。演员回家，角色留在门牌背后。

发布信息草案

标题：每个人都有三个地址
摘要：扩展域并查集的关键是把有限关系拆成有语义的角色地址，再将关系复合改写为连通约束。
标签：并查集、扩展域、关系建模、食物链、二分图