可持久化数据结构

可持久化数据结构大同小异，其核心就在于修改的操作变成加点。

可持久化线段树

引子：静态区间第 $k$ 小。

较为朴素的方法是，开 $n$ 个权值线段树维护前 $i$ 个数，二分“小于等于 $\text{mid}$ 的个数”，然后用第 $r$ 个线段树的值减第 $l-1$ 个的判断。

然后这里面有很多冗余状态，实际上每次插入只会影响一条链，那么就新建一条这样的链，注意链要指向原树（其实是第 $i-1$ 的树）。

值得注意的是，这个二分其实也是不需要的，可以在线段树上跑：像 BST 那样，左边可以就一起往左边，不然就往右走。

const int N = 100010;

struct Seg
{
	int lt[N<<5], rt[N<<5], cnt;
	ll sum[N<<5];
	void build(int &x, int l, int r)
	{
		x = ++cnt;
		if(l == r) return;
		int mid = (l + r) >> 1;
		build(lt[x], l, mid);
		build(rt[x], mid + 1, r);
	}
	int change(int x, int l, int r, int p)
	{
		int Newx = ++cnt; lt[Newx] = lt[x], rt[Newx] = rt[x], sum[Newx] = sum[x] + 1;
		if (l == r) return Newx;
		int mid = (l + r) >> 1;
		if(p <= mid) lt[Newx] = change(lt[Newx], l, mid, p);
		else rt[Newx] = change (rt[Newx], mid + 1, r, p);
		return Newx;
	}
	int query (int L, int R, int l, int r, int p)
	{
		int ans, mid = (l + r) >> 1, x = sum[lt[R]] - sum[lt[L]];
		if(l == r) return l;
		if(p <= x) ans = query (lt[L], lt[R], l, mid, p);
		else ans = query (rt[L], rt[R], mid + 1, r, p - x);
		return ans;
	}
}sgt;

int n, m;
ll a[N], b[N]; int root[N];

int main()
{
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf ("%d", &a[i]), b[i] = a[i];
	sort(b + 1, b + 1 + n);
	int nn = unique(b + 1, b + 1 + n) - b - 1;
	sgt.build(root[0], 1, nn);
	for (int i = 1; i <= n; i++)
	{
		int p = lower_bound(b + 1, b + 1 + nn, a[i]) - b;
		root[i] = sgt.change(root[i - 1], 1, nn, p);
	}
	for (int i = 1; i <= m; i++)
	{
		int l, r, k;
		scanf ("%d%d%d", &l, &r, &k);
		int ans = sgt.query(root[l - 1], root[r], 1, nn, k);
		printf("%lld\n", b[ans]);
	}
	return 0;
} 

可持久化数组

比较基础的，也发挥了其基础的作用：很多都依赖它。

功能就是改某个历史版本中某位的值，访问某位置某个历史版本的值。

用可持久化线段树维护。

const int N = 1e6 + 10;

int n, m, a[N], root[N << 4];

inline ll read()
{
    ll f = 1, x = 0;
	char ch;
    do{ ch = getchar(); if(ch == '-') f = -1;} while(ch < '0' || ch > '9');
    do{ x = x * 10 + ch - '0'; ch = getchar();} while(ch >= '0' && ch <= '9');
    return f * x;
}

struct Seg
{
	int lt[N << 4], rt[N << 4], cnt;
	ll val[N << 4];
	void build (int &x, int l, int r)
	{
		x = ++cnt;
		if (l == r) {val[x] = a[l]; return ;}
		int mid = l + r >> 1;
		build (lt[x], l, mid);
		build (rt[x], mid + 1, r); 
	}
	int change (int x, int l, int r, int p, ll v)
	{
		int Newx = ++ cnt; lt[Newx] = lt[x], rt[Newx] = rt[x], val[Newx] = val[x];
		if (l == r) {val[Newx] = v; return Newx;}
		int mid = l + r >> 1;
		if (p <= mid) lt[Newx] = change (lt[x], l, mid, p, v);
		else rt[Newx] = change (rt[x], mid + 1, r, p, v);
		return Newx;
	}
	
	int query (int x, int l, int r, int p)
	{
		if (l == r) {return val[x];}
		int mid = l + r >> 1;
		if (p <= mid) return query(lt[x], l, mid, p);
		else return query(rt[x], mid + 1, r, p);
	}
	
}T;

int main()
{
	n = read(), m = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	T.build(root[0], 1, n);
	for (int pre, opt, x, i = 1; i <= m; i++)
	{
		pre = read(), opt = read(), x = read();
		if (opt == 1) {root[i] = T.change(root[pre], 1, n, x, read());} 
		else {printf ("%d\n", T.query(root[i] = root[pre], 1, n, x));}
	}
	return 0;
}

可持久化并查集

朴素的并查集就是单纯的数组操作。路径压缩不好维护，考虑按秩合并：按树高合并。

const int N = 1e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	struct node {
		int l, r, dep, fa;
	} t[N * 50];
	int tot, rt[N << 1];
	void build (int &p, int l, int r) {
		p = ++tot;
		if (l == r) { t[p].fa = l; return ;}
		int mid = (l + r) >> 1;
		build (t[p].l, l, mid);
		build (t[p].r, mid + 1, r);
	}
	void add (int &p, int q, int l, int r, int x) {
		p = ++tot; t[p] = t[q];
		if (l == r) { t[p].dep++; return; }
		int mid = (l + r) >> 1;
		if (x <= mid) add (t[p].l, t[q].l, l, mid, x);
		else add (t[p].r, t[q].r, mid + 1, r, x);
	}
	int query (int p, int l, int r, int x) {
		if (l == r) return p;
		int mid = (l + r) >> 1;
		if (x <= mid) return query (t[p].l, l, mid, x);
		else return query (t[p].r, mid + 1, r, x);
	}
	void Merge (int &p, int q, int l, int r, int x, int fa) {
		p = ++tot;
		t[p].l = t[q].l, t[p].r = t[q].r;
		if (l == r) { t[p].dep = t[q].dep; t[p].fa = fa; return; }
		int mid = (l + r) >> 1;
		if (x <= mid) Merge (t[p].l, t[q].l, l, mid, x, fa);
		else Merge (t[p].r, t[q].r, mid + 1, r, x, fa);
	}
	int find (int p, int x) {
		int now = query (p, 1, n, x);
		if (t[now].fa == x) return now;
		else return find(p, t[now].fa);
	}
	void merge (int ver, int x, int y) {
		rt[ver] = rt[ver - 1];
		int fx = find(rt[ver], x), fy = find(rt[ver], y);
		if (t[fx].fa != t[fy].fa) {
			if (t[fx].dep > t[fy].dep) swap(fx, fy);
			Merge(rt[ver], rt[ver - 1], 1, n, t[fx].fa, t[fy].fa);
			if (t[fx].dep == t[fy].dep) add (rt[ver], rt[ver], 1, n, t[fy].fa);
		}
	}
	bool Find(int ver, int x, int y) {
		rt[ver] = rt[ver - 1];
		int fx = find(rt[ver], x);
		int fy = find(rt[ver], y);
		return t[fx].fa == t[fy].fa;
	}
	int main () {
		n = Read(), m = Read();
		build(rt[0], 1, n);
		for (int i = 1; i <= m; i++) {
			int opt = Read();
			if (opt == 1) { int a = Read(), b = Read(); merge(i, a, b); }
			if (opt == 2) { int k = Read(); rt[i] = rt[k]; }
			if (opt == 3) { int a = Read(), b = Read(); printf ("%d\n", Find(i, a, b)); }
		}
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}

剩下的来不及写了。