Day 1

考试。

T1 是神秘构造题，让我们构造一个双射 \(f\)，使得 \(A\subseteq f(A)\)，其中 \(|A|=n-1,|f(A)|=n\)。两者元素均在 \([1,2n-1]\) 之间。

然后好像用 Raney 引理就可以构造出一个双射：假设 \([1,2n-1]\) 是一个环，然后假设选过的值是 \(+1\)，没选过的是 \(-1\)，这个序列的最后一个最大值最保证了其在这里开始的循环序列满足该点就是唯一前缀最大值，所以存在一个双射 \(A\to A\cup\{maxpos+1\}\)，因为 \(maxpos+1\) 处为负，没选过，然后加入一个 \(maxpos+1\) 之后这个序列仍然存在唯一前缀最大值且比原最大值大一。观察其形态不可能由其他的任何函数经过上面映射过来，所以这是一个双射。

T2 看不懂。

T3 就是发现对于一个连通块，我们的罚时次数只有两种可能：\(A\) 或 \(A+1\)。

一个 trival 的想法就是发现对于所有 \(O(k)\) 个集合，它前面其实都对于到根路径模 \(T\) 有一个分界点，两侧的罚时次数分别是 \(A\) 和 \(A+1\)。最多有 \(k\) 个分界点，所以每个集合可以分成 \(O(k)\) 个等价类，每个等价类里面的对于其他集合的罚时次数都是一样的。暴力维护这个东西 + 暴力合并 同集合的 子树 对于其他集合的 罚时次数的 集合就是 \(O(nk^2+qk^2)\) 的，然后如果利用上 \(A\) 和 \(A+1\) 的性质状压（这里需要使用每个同色连通块到其他集合的罚时次数了）一下可以把空间从 \(O(nk^2)\) 压到 \(O(nk)\)。

原题 CF1621H，我觉得看代码或者某些人的题解会更好理解。