启发式合并

我觉得启发式合并真的很需要策略，巨大的思维量。

启发式合并，就是用并查集合并两个节点时，根据节点携带信息的大小 $siz$，来决定合并方向。从而使得合并时遍历节点信息的复杂度稳定在 $O(n\log n)$ 左右。

一般启发式合并的难点还是在于那个并查集指代的信息，要维护节点的什么信息，合并时是否要将信息拎出来计算答案等……总之很有思维量，会很难调，但是时间复杂度很优秀。

1.nfls #4543 交朋友 / 洛谷 P8907 USACO22DEC Making Friends

我的博客

2.nfls #7712 化学反应 / 洛谷 P5578 PA2014 Fiolki

题意

吉丽有 $n$ 种不同的液体物质，和 $n$ 个药瓶（均从 $1$ 到 $n$ 编号）。初始时，第 $i$ 个瓶内装着 $g_i$ 克的第 $i$ 种物质。

吉丽需要执行一定的步骤来配置药水，第 $i$ 个步骤是将第 $a_i$ 个瓶子内的所有液体倒入第 $b_i$ 个瓶子，此后第 $a_i$ 个瓶子不会再被用到。瓶子的容量可以视作是无限的。

吉丽知道某几对液体物质在一起时会发生反应产生沉淀，具体反应是 $1$ 克 $c_i$ 物质和 $1$ 克 $d_i$ 物质生成 $2$ 克沉淀，一直进行直到某一反应物耗尽。生成的沉淀不会和任何物质反应。

当有多于一对可以发生反应的物质在一起时，吉丽知道它们的反应顺序。每次倾倒完后，吉丽会等到反应结束后再执行下一步骤。

吉丽想知道配置过程中总共产生多少沉淀。

$0\le m<n\le 2\times 10^5$，$0\le k\le 5\times 10^5$，$1\le g_i\le 10^9$，$1\le a_i,b_i,c_i,d_i\le n$，$a_i\ne b_i$，$c_i\ne d_i$。

思路

zc 说，如果这个题往启发式合并想，就会是紫的难度。

把一个瓶子 $a$ 内的所有东西倒入 $b$，让人想要并查集维护节点信息的转移。但是这一题要素过多，要维护什么呢？

先看看那个很毒瘤的反应优先级。实则每个反应只会出现一次，因为每次会耗尽 $c,d$ 中的其中一个。

在还没开始倒瓶子之前，每个物质 $c_i$ 是用编号为 $c_i$ 的瓶子装着的。那么条件给出的 $c,d$ 物质之间反应的优先级，等价于含有物质 $c,d$ 的、编号为 $c,d$ 的瓶子可以反应的优先级（反应编号）。

考虑维护，每个瓶子内所含有的所有物质，可以反应的实验编号集合 $reac$，再用并查集维护指向瓶子内的物质集合（F=find_fa(i) 表示 $i$ 被倒到了 $F$ 瓶子里）。

for(int i=1;i<=k;i++)//实验优先级（实验编号）
{ll c,d;scanf("%lld%lld",&c,&d);reac[c].push_back(i);reac[d].push_back(i);
}

那么倒水（合并两个瓶子的物质）的时候，若从 $u$ 倒到 $v$，先合并两个瓶子中的物质到 $v$，然后遍历 $rea{c}_u$ 考虑合并到 $rea{c}_v$。对于实验序号 $X\in rea{c}_u$，即将合并到 $rea{c}_v$，如果 $X$ 的两个反应物质此时“相遇”（即 find_fa(shiyan[X].c)==find_fa(shiyan[X].d)），就把 $X$ 记录下来，在倒 $u$ 到 $v$ 时会发生实验 $X$。

for(int i=1;i<=m;i++)
{if(reac[q[i].u].size()>reac[q[i].v].size())reac[q[i].u].swap(reac[q[i].v]);//启发式合并药瓶ll fu=fz(q[i].u),fv=fz(q[i].v); fa[fu]=fv;//合并瓶子的物质tem.clear();//待做实验集合for(auto x:reac[q[i].u]){if(fz(ord[x].c)==fz(ord[x].d))tem.push_back(x);//两种物质在一起可以反应 else reac[q[i].v].push_back(x);}...
}

由于可能会有很多实验的两种物质在此时“相遇”，因此把这些实验编号用临时数组记下来，按照实验编号（即优先级）排序，对每个物品计算沉淀即可。

说的不容易，写起来也难。

代码1

#include<bits/stdc++.h>
#pragma GCC optimise(2)
#pragma GCC optimise(3,"Ofast","inline")
using namespace std;
#define ll long long
const ll N=2e5+2,M=5e5+9;
ll n,m,k;
ll a[N];
struct que
{ll u,v;
}q[N];
struct order
{ll c,d;
}ord[M];
ll fa[N];
ll fz(ll x)
{while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;
}
vector<ll>reac[N];
int main()
{scanf("%lld%lld%lld",&n,&m,&k);for(int i=1;i<=n;i++){fa[i]=i;scanf("%lld",&a[i]);}for(int i=1;i<=m;i++){ll u,v;scanf("%lld%lld",&u,&v);q[i]=(que){u,v};}for(int i=1;i<=k;i++){ll c,d;scanf("%lld%lld",&c,&d);ord[i]=(order){c,d};reac[c].push_back(i);reac[d].push_back(i);}ll ans=0;vector<ll>tem;for(int i=1;i<=m;i++){if(reac[q[i].u].size()>reac[q[i].v].size())reac[q[i].u].swap(reac[q[i].v]);//启发式合并药瓶ll fu=fz(q[i].u),fv=fz(q[i].v);//物质编号 fa[fu]=fv;tem.clear();for(auto x:reac[q[i].u]){if(fz(ord[x].c)==fz(ord[x].d))tem.push_back(x);//两种物质在一起可以反应 else reac[q[i].v].push_back(x);}sort(tem.begin(),tem.end());for(auto x:tem){ll cost=min(a[ord[x].c],a[ord[x].d]);a[ord[x].c]-=cost;a[ord[x].d]-=cost;ans+=cost*2;}}printf("%lld",ans);return 0;
}

但是这个题思维量和处理难度那么大，为什么只有绿呢？其实这题有一个比较明显的建模：因为瓶子 $a$ 的东西全部倒进 $b$，$a$ 以后不再使用，因此两种物质指向的是一个瓶子；一个混装多种物质的瓶子 $e$ 倒进另外一个瓶子 $f$，指向的也是 $f$ ——这呈现出一棵树的结构！

不妨把两个瓶子倒进一个新的瓶子！我们让只装着物质 $i$ 的瓶子编号 $i$ 作为叶节点，为两瓶倒在一起指向一个新的节点，维护 $cu{p}_u$ 表示瓶子 $u$ 倒进了新建瓶子后的新编号。

（建议来这篇题解读图）

这样我们就建好了树。因为上文我们说每个反应只会发生一次的结论，所以我们考虑枚举每个实验编号。对于初始在叶节点的物质们，反应 $i$ 的两个物质 $c_i,d_i$ 有机会发生反应，当且仅当在树上他们存在 $\mathrm{lca}$。

而在这棵倒水的树上，显然 $\mathrm{lca}(c_i,d_i)$ 深度更大的反应 $i$ 会优先反应。因此把每个实验当做询问包起来，按照 $de{p}_{\mathrm{lca}(c_i,d_i)}$ 的深度大小作为第一关键字、反应优先级（编号）作为第二优先级排序，依次进行每个实验。

代码2

#include<bits/stdc++.h>
#pragma GCC optimise(2)
#pragma GCC optimise(3,"Ofast","inline")
using namespace std;
#define ll long long
const ll N=2e5+2,M=5e5+9,O=7e5+9;
ll n,m,k;
ll cup[N],a[N];
struct chem
{ll x,y;ll dep;//越深的先遇到 ll id;//反应优先级 
}p[M];
ll tot;
bool cmp(chem x,chem y)
{if(x.dep!=y.dep)return x.dep>y.dep;return x.id<y.id;
}
vector<ll>G[O];
bool vis[O];
ll dep[O],f[O][22];
void dfs(ll u,ll fa)
{vis[u]=1;dep[u]=dep[fa]+1;f[u][0]=fa;for(int i=1;(1<<i)<=dep[u];i++)f[u][i]=f[f[u][i-1]][i-1];for(auto v:G[u]){dfs(v,u);}
}
ll lca(ll x,ll y)
{if(dep[x]<dep[y])swap(x,y);for(int i=21;i>=0;i--)if(dep[x]-(1<<i)>=dep[y])x=f[x][i];if(x==y)return x;for(int i=21;i>=0;i--){if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}}return f[x][0];
}
int main()
{scanf("%lld%lld%lld",&n,&m,&k);for(int i=1;i<=n;i++){cup[i]=i;scanf("%lld",&a[i]);}for(int i=1;i<=m;i++){ll u,v,t=n+i;//t为u倒进v之后的树根 scanf("%lld%lld",&u,&v);G[t].push_back(cup[u]);G[t].push_back(cup[v]);cup[v]=t;}for(int i=n+m;i>=1;i--)if(!vis[i])dfs(i,0);for(int i=1;i<=k;i++){ll u,v,LCA;scanf("%lld%lld",&u,&v);LCA=lca(u,v);if(!LCA)continue;p[++tot]=(chem){u,v,dep[LCA],tot};}sort(p+1,p+tot+1,cmp);ll ans=0;for(int i=1;i<=tot;i++){ll cost=min(a[p[i].x],a[p[i].y]);a[p[i].x]-=cost;a[p[i].y]-=cost;ans+=2*cost;}printf("%lld",ans);return 0;
}

3.nfls #4572 相邻点查询 / AT_abc350_g Mediator

题意

请注意特殊的输入格式。同时，请注意内存限制比通常更小。

有一个包含 $N$ 个顶点 $1,2,\dots ,N$ 的无向图，初始时没有任何边。
请对该图处理以下 $Q$ 个查询。

1 $u$ $v$

类型 $1$：在顶点 $u$ 和顶点 $v$ 之间添加一条边。
在添加边之前，$u$ 和 $v$ 属于不同的连通分量（也就是说，图始终是一片森林）。

2 $u$ $v$

类型 $2$：如果存在同时与顶点 $u$ 和顶点 $v$ 相邻的顶点，则输出其编号，否则输出 $0$。
由于图始终是一片森林，可以证明对于该查询的答案是唯一的。

但是，上述查询是经过加密后给出的。
原始查询由 $3$ 个整数 $A,B,C$ 定义，基于此给出加密后的查询 $a,b,c$。
对于类型 $2$ 的查询，第 $k$ 个（从前往后数）查询的答案记为 $X_k$。此外，定义 $k=0$ 时 $X_k=0$。
请根据给定的 $a,b,c$ 按如下方式解密得到 $A,B,C$：

• 设在该查询之前已经给出的类型 $2$ 查询的个数为 $l$（不包括当前查询）。此时，按如下方式解密：
  • $A=1+(((a\times (1+X_l))\mathrm{mod}998244353)\mathrm{mod}2)$
  • $B=1+(((b\times (1+X_l))\mathrm{mod}998244353)\mathrm{mod}N)$
  • $C=1+(((c\times (1+X_l))\mathrm{mod}998244353)\mathrm{mod}N)$

$2\le N\le 10^5$，$1\le Q\le 10^5$，$1\le u<v\le N$，$0\le a,b,c<998244353$。

思路

合并两个点，根据 find_fa(u) 和 find_fa(v) 的连通块大小决定 $u$ 是否是 $v$ 的父亲。不妨钦定 siz[find_fa(u)]>siz[find_fa(v)]，我们直接 dfs(v,u) 重构 $v$ 作为 $u$ 的子树，然后建边 $(u,v)$，合并 fa 和 siz。

对于查询，因为在树上两点之间只有唯一路径，因此和 $u$ 和 $v$ 同时相邻的节点只有一个。这个节点只会是：

• 同时为 $u$ 的父亲与 $v$ 的儿子（$u$ 和 $v$ 在同一链上）；
• 同时为 $v$ 的父亲与 $u$ 的儿子（$u$ 和 $v$ 在同一链上）；
• 同时为 $u$ 和 $v$ 的父亲（$\mathrm{lca}(u,v)$）。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+9;
ll n,Q;
vector<ll>G[N];
ll fat[N];
ll fa[N],siz[N];
ll fz(ll x)
{while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;
}
void dfs(ll u,ll fa)
{fat[u]=fa;for(auto v:G[u]){if(v==fa)continue;dfs(v,u);}
}
void join(ll u,ll v)
{ll fu=fz(u),fv=fz(v);if(siz[fu]<siz[fv]){swap(u,v);swap(fu,fv);}dfs(v,u);//启发式合并 重构 siz[fu]+=siz[fv];fa[fv]=fu;G[u].push_back(v);G[v].push_back(u);
}
int main()
{scanf("%lld%lld",&n,&Q);for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;ll lans=0;while(Q--){ll op,u,v;scanf("%lld%lld%lld",&op,&u,&v);op=1+((op*(1+lans))%998244353)%2;u=1+((u*(1+lans))%998244353)%n;v=1+((v*(1+lans))%998244353)%n;if(op==1)join(u,v);else{lans=0;if(fat[u]==fat[v]&&fat[u])lans=fat[u];else if(fat[fat[u]]==v)lans=fat[u];else if(fat[fat[v]]==u)lans=fat[v];printf("%lld\n",lans);}}return 0;
}