题目非私密模拟,可以公开博客。
Problem 1
取 $G$ 的任一 DFS 树 $T$,考虑一条边 $(u,v) \in E$ 且 $d_u > d_v$,由于 DFS 树中没有横叉边,因此 $u \in \mathrm{subtree}(v)$,考虑删去 $u,v$ 后整棵树会分成以下几个部分:
- $v$ 到根以及上面挂着的部分,记作 $H$。
- $u$ 到 $v$ 路径及上面挂着的部分,记作 $M$。
- $u$ 的所有子树,记作 $L_i$。
问题等价于判断这些部分有没有全部被连在一起。
首先,判断 $H$ 和 $M$ 有没有被连起来是简单的:预处理 $u$ 到其 $2^k$ 次祖先的这一段以及上面挂着的东西中,不算 $u$,连出去的边最高能到哪里。如果这个深度突破了 $v$,那么 $H$ 和 $M$ 就连起来了。
然后考虑 $H$ 和 $L_i$ 的连接。这个也是简单的:DFS 的时候预处理出每个子树里面,连上去最高到哪里,如果突破了 $v$ 就说明连起来了。因此,我们可以把所有边按照 $u$ 分类,然后按照 $v$ 从深到浅的顺序考虑,那么每个 $L_i$ 就会逐渐地和 $H$ 连起来,扫描线即可。
最后就是 $M$ 和 $L_i$。既然我们之前已经按照 $v$ 从深到浅考虑了,所以只要求出 $v$ 深度的临界点即可。这个可以通过将所有 $u$ 按照从浅到深的顺序考虑,然后用一个线段树来查询每个子树往上,最深连到了哪里。
注意几个特殊情况:$H = \varnothing$($v$ 是根),$M = \varnothing$($v$ 是 $u$ 的父亲)和都是空的。前面两个都可以直接处理;都是空的的情况分类讨论一下就好了,因为这个时候可能会有不在 $H,M,L_i$ 中的子树。
时间复杂度 $\Theta(n \log n)$
Problem 2
平方运算相当于指数乘二,因此其循环节长度的 $\operatorname{lcm}$ 为 $2^x \pmod {998244352}$ 的循环节长度。
$998244352=7\times 17 \times 2^{23}$,其循环节长度应该很短,具体跑一下发现循环节长度为 $24$。
使用线段树维护,对于一个 $a_i$,如果它当前不在循环节上($a_i$ 的变化可能是 $\rho$ 型的),那么可以暴力修改。
否则线段树上每个区间维护一个长为 $24$ 的环,每次平方就将环往前转一格即可。复杂度 $\Theta(cq log n)$,其中 $c=24$。
Problem 3
利用给定条件不难求出树的质心 $c$(可以将每条边看做质量在中点处然后求加权平均),转动惯量 $I$(中点距离质心 $d$ ,长度 $l$ 的边的转动惯量为 $I=\frac{1}{12}\eta l^3 + \eta ld^2$ ,然后对所有边求和)和外力矩 $M$ (设质心到边中点矢量为 $r$,则这条边的力矩为 $r \times f_i$,其中为 $\times$ 向量外积,然后对所有边求和),并求出角加速度 $\beta=M/I$,进而得到初始角度 $\theta=\frac{1}{2}\beta t^2$ 和角初速度 $\omega=-\beta t$,并得到时刻 $T$ 的角度 $\theta_T = \frac{1}{2}\beta(t-T)^2$。
对于树质心的运动,求出结束时加速度 $a_t = F_t/M = r(\cos \theta, \sin \theta)$,则时刻 $T$ 的加速度为 $a_T = r(\cos(\theta + \frac{1}{2} \beta(t-T)^2), \sin(\theta + \frac 12 \beta(t-T)^2))$,由于初始时质心速度为 $0$ ,则质心在这段时间的位移量为:
$$\int_0^t \int_0^x a_T \mathrm d T \mathrm dx = -\frac 12 \int_{t^2}^0 r(\cos(\theta+\frac 12\beta\alpha), \sin(\theta+\frac 12\beta\alpha)) \mathrm d\alpha$$
最后的积分根据 $\beta$ 是否为 $0$ 讨论后可以求出。
于是问题得到了解决,时间复杂度 $\Theta(n)$。
Problem 4
容易将问题分成两个部分:第一部分找出 $A$ 的数的集合,而第二部分找出 $A$ 的顺序。考虑到给出的次数限制,平均每一次询问我们需要利用到超过一位的信息,首先考虑找出集合的部分,我们可以将每个数标为 $0$ 或 $1$,那么每次操作即是求不超过 $M$ 个数之和。
考虑一个经典问题,给定 $L$ 个数构成的 $0/1$ 串,如何通过查询子集和确定该串中每个位置的取值,朴素的解法需要查询线性次,而实际上我们可以构造出查询 $O(\frac{L}{\log L})$ 次的方法:不妨假设我们能用 $a - 1$ 次询问和 $1$ 次额外的询问总和的操作得出长度为 $b$ 的序列的取值,我们就可以用 $2a - 1$ 次询问和 $1$ 次额外的询问总和的操作得出长度为 $2b + a − 1$ 的序列的取值。
这是通过先查询前 $b$ 个数的和 $s$,随后对于每一个用来查询长度为 $b$ 的序列的询问,不妨假设其在前 $b$ 个位置的和为 $u$,接下来的 $b$ 个位置和为 $v$,我们分别查询 $s - u + v$ 和 $u + v$,容易发现此时我们在第二次询问中还可以额外多查询一个位置的值,仍然可以还原 $u$ 和 $v$,因此我们就可以多询问出 $a - 1$ 个位置的值了,这样递推下去便是一个 $O(\frac{L}{\log L})$ 次查询的方法。而对于任意长的给定序列,我们可以将其拆成若干小段来进一步减少所需的次数。在本题中,有一个分值较大的测试点便是给这一部分解法(第二部分采取暴力方法)。
经过思考可以看出,当前问题下的最本质不同是一个随机位置是 $0$ 和 $1$ 的概率是不同的,因此直接采取上述方法会浪费许多次数。
然而,如果我们能够将长度为 $N$ 的序列切成若干段,每段恰包含一个 $1$,那么每一段中随机选一个子集值为 $0$ 和 $1$ 的概率就均等了,而我们一开始随机均等划分每个长度为 $M$ 的段只需要 $O(N/M)$ (期望情况下常数在 2.3 以内)次即可得到若干这样的段。在朴素的情况下,我们对于每一段都需要二分。然而实际上,由于每一段二分时概率均等,我们可以利用经典的求 $0/1$ 序列方法进行优化,即对二分的过程进行并行。经过简单分析,这样可以在这一部分做到 $M \log \log M$ 级别的询问次数。在这一部分,还有一个小的常数优化是我们可以每次选择长度不超过 $2M$ 的序列,在每次询问时只需询问元素个数较小的一侧即可(我们总要询问总和)。
有了以上铺垫,第二部分也可以用 $M \log \log M$ 次询问次数解决了:对于第二部分,我们可以一层层二分每个元素对应的位置,每次将所有可能的位置减半填上该元素。由于每个位置对应恰好一个元素,在每一层我们总能用元素将询问的位置填满,这样在自上至下的第 $i$ 层就是询问长度为 $2^i$ 的 $0/1$ 序列的元素值。略微精细的实现有助于减少最终所需的询问次数。