\(\textbf{D1T2}\)

很奇妙的一题，不过我不会。可以看 xhgua 的博客。

\(\textbf{D5T3}\)

模拟赛放 Ynoi，兄弟。

\(\textbf{D5T3.1 Description}\)

实现一个数据结构，要求实现三个操作：

在图中将两个点连边；
回退到某个历史版本；
查询所有点 \(x\) 可到达的店中所有店中点权第 \(k\) 大。

\(1\le n,m \le 10^5\) 。

\(\textbf{D5T3.2 Solution}\)

很显然的需要使用并查集。口胡了一个启发式合并：每个并查集维护一个 std::vector 当做平衡树维护点权集合。保存所有历史版本即可。但是数据太毒瘤了，全 RE。

后来发现不写撤销操作能拿分，\(14\text{pts}\) 滚粗。

暴力的瓶颈在于空间。

本题最大的空间开销就是撤销操作需要回到历史版本。

注意到不强制在线，考虑把所有的询问离线下来。

用 std::vector 之类的东西保存所有需要回退的版本编号，只有当当前版本在后续操作中用得到时才保存它。这样可以节省许多不必要的空间开销。

当然这个东西随便卡。而且代码也很难写。

容易将上述思路的「后续操作用得到时保存」转化为「不保存，直接以当前版本为基础完成所有后续操作」。

这和 dfs 是非常类似的：遍历，回溯。于是有一个新的思想：操作树。

操作树就是所有操作组成的树。对于所有操作二，把当前操作编号和所给历史版本时间戳连边，对于操作一和三，把当前操作和上一个操作连边。

读入完询问之后对于操作树遍历一边即可。写一个类似可撤销并查集的东西即可，三个操作直接暴力干。

本题的原题是 Ynoi。因此考虑分块。区间第 \(k\) 大，很显然的值域分块。

点权离散化之后最多 \(10^5\) 个值，对这 \(10^5\) 个值开桶然后对桶分块。

具体地，令 \(\text{cnt}(rt, k)\) 表示根为 \(rt\) 的并查集中，点权属于第 \(k\) 个块所表示的区间的个数。那么点权 \(k\,\text{th}\) 可以轻易地解决：整块扫描过去，直到 \(\sum_{i=1}^{p-1}\text{cnt}(rt,i)\le k\) 且 \(\sum_{i=1}^p\text{cnt}(rt,i)> k\) 。然后扫描原数组（离散化后）上第 \(p\) 个块对应的区间，从小到大枚举属于该并查集的值，什么时候刚好 \(k\) 了直接 break 就行。

细节稍微注意一下，只要不是和我一样把乘写成除就行（）

\(\textbf{D5T3.3 AC Code}\)

#include <bits/stdc++.h>

// FastIO

typedef long long i64;
constexpr int N = 1e5 + 5;
constexpr int B = 2000;
int n, m, siz[N], fa[N], tot, ans[N];
unsigned short cnt[N][N / B + 5];

inline int find(int x) {
	return x == fa[x] ? x : find(fa[x]);
}

struct Node { int val, id; } a[N];
struct que { int opt, x, y; } q[N];

struct Edge { int to, nxt; } E[N];
int head[N], idx;

inline void addEdge(int x, int y) {
	E[++idx] = Edge{y, head[x]}, head[x] = idx;
}

inline void mrg(int x, int y) {
	if(siz[x] > siz[y]) x ^= y ^= x ^= y;
	fa[x] = y, siz[y] += siz[x];
	for(int i = 1; i <= tot; i++) {
		cnt[y][i] += cnt[x][i];
	}
}

inline void del(int x, int y) {
	if(siz[x] > siz[y]) x ^= y ^= x ^= y;
	fa[x] = x, siz[y] -= siz[x];
	for(int i = 1; i <= tot; i++) {
		cnt[y][i] -= cnt[x][i];
	}
}

inline int qry(int x, int k) {
	int pos, res = 0;
	x = find(x);
	if(siz[x] < k) return -1;
	for(int i = 1; i <= tot; i++) {
		if(k > cnt[x][i]) k -= cnt[x][i];
		else { pos = i; break; }
	}
	for(int i = (pos - 1) * B + 1; i <= pos * B; i++) {
		if(find(a[i].id) == x && !(--k)) res = a[i].val;
	}
    return res;
}

inline void dfs(int u) {
	bool tag = 0;
	int opt = q[u].opt, x = q[u].x, y = q[u].y;
	if(opt == 1) {
		x = find(x), y = find(y);
		if(x ^ y) {
			mrg(x, y);
			tag = 1;
		}
	} else if(opt == 3) ans[u] = qry(x, y);
	for(int i = head[u]; i; i = E[i].nxt) dfs(E[i].to);
	if(tag) del(x, y);
}

signed main() {
	read(n, m);
	tot = (n - 1) / B + 1;
	for(int i = 1; i <= n; i++) {
		read(a[i].val);
		a[i].id = fa[i] = i;
		siz[i] = 1;
	}
	std::sort(a + 1, a + n + 1, [](Node& lhs, Node& rhs) {
		return lhs.val < rhs.val;
	});
	for(int i = 1; i <= n; i++) {
		cnt[a[i].id][(i - 1) / B + 1]++;
	}
	for(int i = 1; i <= m; i++) {
		read(q[i].opt);
		if(q[i].opt == 2) {
			read(q[i].x);
			addEdge(q[i].x, i);
		} else {
			read(q[i].x, q[i].y);
			addEdge(i - 1, i);
		}
	}
	dfs(0);
	for(int i = 1; i <= m; i++) {
		if(q[i].opt == 3) {
			writeln(ans[i]);
		}
	}
	return flush(), 0;
}

原题链接：[Ynoi2014] 等这场战争结束之后

\(\textbf{D5T4}\)

\(\textbf{D8T1}\)

模拟赛 A 题放黑你见过吗？

标签：Summer,Training,int,siz,cnt,textbf,做题,text,操作
From： https://www.cnblogs.com/Matrixqwq/p/17566340.html

X-Camp 2023 Summer Training 做题泛记