资讯详情

前置芝士

并查集

可持久化数组

算法内容

P3402 【模板】可持久化并查集

可持久化并查集和并查集的最大区别是多出了返回之前版本的操作。

版本之间实质上的差别是 fa 数组不同。

根据数据范围，我们发现每个版本的 fa 数组都存一遍是不可行的，于是联想到可持久化。

于是我们对 fa 数组进行可持久化。

但是只是这样还是不够的。

回顾一下，并查集不做优化时的时间复杂度较高。在本题中，应采用怎样的优化方法呢？

容易想到我们平时优化并查集最常用的方法：路径压缩。在普通并查集中，路径压缩有着优秀的时间复杂度，查询时的复杂度是均摊 \(O(n\alpha)\) 的（注意是均摊）。

但是均摊在可持久化中是致命的，因为均摊复杂度优秀并不代表单次时间复杂度也一定优秀，所以可能会出现某次查询的复杂度是 \(O(n)\) 的，而毒瘤的出题人会抓住时机，让你的代码在这两个版本中来回横跳，让你的代码 T 飞。

那主播主播有没有单次时间复杂度也是比较优秀的优化方法呢，有的兄弟有的，并查集的优化方法当然是不止一个的了，还有一个按秩合并，是单次严格复杂度 \(O(\log n)\) 的强势优化方法。

按秩合并主要有两种方式：按深度和按大小。这里就以按深度为例，因为很好理解而且我们也不能保证出题人不会甩给我们一条链。

为了省事，这么做的复杂度证明这里不给出。

那么具体的，对于一次修改，我们需要新建 2 个版本。

首先将这个版本中的 \(\text{fa}_v\)​ 变为 \(u\)，接着，我们需要修改 \(\text{dep}_u\)​。

这么做的复杂度是很优秀的，可以稳过这题。

模板代码

#include <bits/stdc++.h>
using namespace std;struct node {int ls,rs,fa,dep;
} tree[6000011];int n,m,cnt;
int rt[300011];int build(int l,int r) {int u = ++cnt; if (l == r) {tree[u].fa = l;return u;}int mid = (l + r) / 2;tree[u].ls = build(l,mid);tree[u].rs = build(mid + 1,r);return u;
}int query(int u,int l,int r,int x) {if (l == r)return u;int mid = (l + r) / 2;if (x <= mid)return query(tree[u].ls,l,mid,x);elsereturn query(tree[u].rs,mid + 1,r,x);
}int find(int u,int v) {int nu = query(rt[v],1,n,u);if (tree[nu].fa == u)return nu;return find(tree[nu].fa,v);
}int addnode(int u) {tree[++cnt] = tree[u];return cnt;
}int hb(int u,int l,int r,int x,int f) {int k = addnode(u);if (l == r) {tree[k].fa = f;return k;}int mid = (l + r) / 2;if (x <= mid)tree[k].ls = hb(tree[u].ls,l,mid,x,f);elsetree[k].rs = hb(tree[u].rs,mid + 1,r,x,f);return k;
}int add(int u,int l,int r,int x) {int k = addnode(u);if (l == r) {tree[k].dep++;return k;}int mid = (l + r) / 2;if (x <= mid)tree[k].ls = add(tree[u].ls,l,mid,x);elsetree[k].rs = add(tree[u].rs,mid + 1,r,x);return k;
}void merge(int u,int x,int y) {rt[u] = rt[u - 1];x = find(x,u);y = find(y,u);if (tree[x].fa != tree[y].fa) {if (tree[x].dep > tree[y].dep)swap(x,y);rt[u] = hb(rt[u - 1],1,n,tree[x].fa,tree[y].fa);if (tree[x].dep == tree[y].dep)rt[u] = add(rt[u],1,n,tree[y].fa);}
}int main() {scanf("%d%d",&n,&m);rt[0] = build(1,n);for(int i=1;i<=m;i++) {int opt,x,y;scanf("%d%d",&opt,&x);if (opt == 1) {scanf("%d",&y);merge(i,x,y);}else if (opt == 2)rt[i] = rt[x];else {scanf("%d",&y);int a = find(x,i - 1);int b = find(y,i - 1);if (tree[a].fa == tree[b].fa)puts("1");elseputs("0");rt[i] = rt[i - 1];}}return 0;
}

拓展

NOI2018 D1T1 归程

这题我还不会做，待会再写。