X-Camp 2023 Summer Training

Matrixqwq's Blog / 2023-07-19 / 原文

由于我懒，本 Blog 只记录暑期集训的难题 & 趣题，当然大部分难题我都不会做。

当然这篇 Blog 更倾向日记风格。

补题列表：D1T2 | D5T1 | D7T2 | D8T1

杭师大的饭虽然不难吃，但是感觉不如 wz，不甚满意/ng

收手机，有点伤心。/ng

$\textbf{7.10 D1T2}$

咕咕咕~

$\textbf{7.11}$

今晚九点，不见不散，郑荣叫爹！

扑克真的很好玩！尤其是看到 zr 睁大眼睛说你为什么还有三张 A 的时候（

真的是小丑/cf

$\textbf{7.14 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 = 3300;
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;
            break;
        }
	}
    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;
}

实际块长为 $1000$ 左右的时候我的代码跑的最快。但是原题卡空间，所以块长设的比较大。

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

$\textbf{7.15 第一次测试游寄}$

考试时将是 5:30 - 9:00，时间挺长的。赛前还在想能不能 AK（

先开 T1。题目要求 $\min\sum|\frac{x_i-x}{v_i}|$，绝对值之和显然要转化成和中位数相关的问题。思考了 10min 怎么把这玩意和中位数联系上来。然后发现读错题了，要求的是 $\min\max\sum|\dots|$。这不一眼？直接二分答案，check 也很好写，对每个 $i$ 都能写出一个一次不等式，联立一下看一下解集是否非空即可。0.5h 切 T1，有点慢了（

开 T2，感觉像个 dp，好像有点难先放着。然后看 T3，这是什么？感觉很典但是一时没法看出什么思路。T4：什么神秘图论？我 Tarjan 都没学过我玩个毛线啊？

想了想还是先开 T2。不会 dp，开始想暴力。最开始思考对每个颜色处理需要达到其最大值的最小操作次数。赛时比较紧张感觉这个没错。然后代码不太会写，停了好久。大概 7:00 左右头脑突然清醒：这不随便 Hack？换了个思路，考虑莫队。类似莫队的区间转移，动态地去维护所有满足条件的区间，$ans$ 即为过程中所有颜色的出现次数取 $\max$ 即可。然后思考对什么分块。然后发现又降智了：询问都没有写什么莫队啊？这不直接双指针？码码码！10 min 搞定。

这个时候大概过了 1h，打算冲 T3。最小值最大考虑二分。T1 T3 全是二分，这是二分专场吗？首先容易想到一个 $\mathcal O(n^3)$ 左右（std::sort 带 $\log$）的 check：扫描 $[1,n]$，如果当前位置的高度不够，就选取覆盖当前点的所有区间中右端点前 $k$ 大的区间然后暴力加就行。差分一下很容易就能做到 $\mathcal O(n^2)$。暴力的瓶颈在于相同的区间被多次查询，即使当前区间已经被用过，或者不可能覆盖以后的点了。

事实上这个时候已经逼近正解了，但是之前模拟赛做过一道题，是通过链表删去不可能决策来避免空循环 TLE。这个思路影响了我，所以考场上我写的是链表：把右端点小于当前点和已经被该点使用的区间删去，这样每次只需要遍历链表，而且很多点是不用加区间的，完全跑不满。加了几个剪枝，手搓了一个样例，连写带调总共大概花了 1.5h。顺便吐槽题目样例是真的水，我考场上任意时刻的代码都能通过样例。总时间复杂度 $\mathcal {O}(n^2\log n\log V)\sim \mathcal{O}(n\log n\log V)$。

T4？你为我会做？打了个爆搜，挂了，懒得鸟他。检查了一下所有文件读写就没了。还有 1h，扫雷启动！同时看到瓜在左边打 T4，隐隐约约在代码里看到一个 Tarjan：果然不是我能碰的题。瓜写完 T4 又回来写 T3，真的是逊，连 T3 都没写/cf

赛后一问，发现 T3 提高二班讲过。czy & cmy & fzy 一起嘲讽我和瓜，伤心，我是不是要垫底了？

预估：$100 + 100 + [60, 100] + 0 = [260, 300]$
实际：$100 + 100 + 100 + 0 = 300$

一分没挂！T3 暴力甚至在原题拿到了最优解，虽然后来被抢了qwq

提高二班三个 Joker T3 都挂了/cf，写过原题都挂，真的是 Joker。但是 wyz 没挂，太强了！

貌似是 wz 分最高的？瓜挂了 80，惨。cmy T1 文件名打错了，虽然很惨但是真的很好笑（