Ynoi2014 等这场战争结束之后

题目大意

有 \(n\) 个点，点有点权，维护一个完全持久化的数据结构并支持：

• 将点 \(x\) 和 \(y\) 之间连接一条边。
• 询问点 \(x\) 所在的连通块的第 \(k\) 小权值。

数据范围：\(1\le n,q\le 10^5,0\le a_i\le 10^9\)。

时间限制：500ms，空间限制：20 MB

思路

写一种比较简单的做法。

先不考虑完全持久化。

先把权值离散化，然后按照权值分块。

对于第一个操作，我们可以使用并查集来维护，对于每个节点维护 \(O(\frac{n}{B})\) 个块，记录其所在连通块内在这个块中出现的权值的数量，每次合并时直接将对应块相加。

这样子一次合并的复杂度是 \(O(\frac{n}{B})\) 的，对于操作 3 的查询也是 naive 的。

对于持久化，有一个经典做法：建出操作树。

那么我们就需要维护一个可撤销并查集，然后按照上述方式来做。

但是这个题的空间限制只有 20MB，所以要卡卡块长，大概取 \(B=\frac{n}{30}\) 左右。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 1, SIZ = 3334;
int n, m, M, cnt, Lst[N];
int head[N + N], nxt[N + N], to[N + N], tcnt;
inline void addedge(int x, int y) {nxt[++tcnt] = head[x], to[tcnt] = y, head[x] = tcnt;}
int tot, top, ans[N];
pair<int, int> op[N], que[N], stk[N], val[N];
int fa[N], siz[N];
short blk[N][31];
inline int FindSet(int x) {return fa[x] == x ? x : FindSet(fa[x]);}
inline void merge(int x, int y) {
	x = FindSet(x), y = FindSet(y);
	if(x == y) return;
	if(siz[x] > siz[y]) swap(x, y);
	fa[x] = y, siz[y] += siz[x];
	for(int i = 1; i <= M; i++) blk[y][i] += blk[x][i];
	stk[++top] = {x, y};
}
inline void del(register int K) {
	while(top > K) {
		register int x = stk[top].first, y = stk[top].second; top--;
		siz[y] -= siz[x]; for(int i = 1; i <= M; i++) blk[y][i] -= blk[x][i];
		fa[x] = x;
	}
}
inline void dfs(register int x) {
	register int K = top;
	if(x > 0) merge(op[x].first, op[x].second);
	for(int p = head[m + x]; p; p = nxt[p]) {
		int t = to[p], x = FindSet(que[t].first), y = 0, k = que[t].second;
		if(k > siz[x]) {ans[t] = -1; continue;}
		for(register int i = 1; i <= M; i++) {
			if(k > blk[x][i]) k -= blk[x][i];
			else {y = i; break;}
		}
		for(register int i = (y - 1) * SIZ + 1; i <= y * SIZ && k; i++) if(FindSet(val[i].second) == x) k--, ans[t] = val[i].first;
	} 
	for(int p = head[x]; p; p = nxt[p]) dfs(to[p]);
	if(x > 0) del(K);
}
int main() {
	#ifdef ddxrS    
		freopen("sample.in", "r", stdin);
		freopen("sample.out", "w", stdout);
	#endif
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin>>n>>m; M = (n + SIZ - 1) / SIZ; cerr<<M<<'\n';
	for(register int i = 1; i <= n; i++) cin>>val[i].first, val[i].second = i;
	sort(val + 1, val + n + 1);
	for(register int i = 1; i <= n; i++) {
		fa[i] = i, siz[i] = 1;
		blk[val[i].second][(i - 1) / SIZ + 1]++;
	}
	for(register int i = 1, opt, x, y, lst = 0; i <= m; i++) {
		cin>>opt>>x;
		if(opt == 1) cin>>y, addedge(lst, cnt + 1), op[lst = ++cnt] = {x, y}, Lst[i] = cnt;
		else if(opt == 2) lst = Lst[x], Lst[i] = lst;
		else if(opt == 3) cin>>y, addedge(m + lst, ++tot), que[tot] = {x, y}, Lst[i] = Lst[i - 1];
	}
	dfs(0);
	for(register int i = 1; i <= tot; i++) cout<<ans[i]<<'\n';
    cerr<<clock() * 1.0 / CLOCKS_PER_SEC<<'\n';
	return 0;
}