CXOI R5 题解

RainRecall · 2025-11-17 21:38:07 · 个人记录

A

::::info[提示 1] 不同的左链链顶数量其实是路径上为其父亲右儿子的点数量加一。 ::::

::::info[提示 2] 一个点不可能被操作两次。 ::::

::::success[正解] 考虑算出交换每一个点对答案产生的价值变化量，按照其排序，贪心选取在一定次数以内的最大的一些整数就好了。

注意答案可能超过 int 范围。 ::::

B

::::info[提示 1] 无法获取 n 具体的值，而变量位只有一个，意味着二分法等方法完全失效了，那应当采用什么方法呢？ ::::

::::success[正解] 牛顿迭代可以解决此问题。

具体来说，我们取一个初始值 x，根据牛顿迭代的式子：

x'\leftarrow x-\frac{f(x)}{f'(x)}

构造函数 f(x)=x^2-n，那么：

x'\leftarrow x-\frac{x^2-n}{2x}

转化为计算器语言如下：

MR * MR - N / 2 / MR = M-

重复此过程若干次可以通过此题。 ::::

C

::::info[提示 1] 不考虑权值的限制如何做？ ::::

::::info[提示 2] 不考虑权值限制时，将排列划分成若干个升序连续段，则含有逆序对的区间表示出来是怎样的？有什么性质？ ::::

::::info[提示 3] 权值的意义到底是什么？ ::::

::::info[提示 4] 是否存在一种满足若干升序连续段的限制，且同时使得权值最优的构造？ ::::

::::success[正解] 性质 1：权值是最长下降子序列。证明如下：

考虑这样一种刻画方式：令 f_i 表示当前长度为 i 的下降子序列中，最后一个元素的最大值。初始 f_i=-\infty。每次加入一个元素 x 后，考虑用其更新所有 f_i：若 x>f_{i-1}，不能更新；若 x<f_{i-1}，那么可以用 x 更新 f_i。我们注意到 f 是单调下降的，也就是说，实际上只有小于和大于交界处的那次更新是有用的，观察这个过程，发现这恰好和“删除 S 中比它小的数中最大的数”相同，所以最后的 |S| 就是最大的 i 使得 f_i\neq -\infty，也就是最长下降子序列，于是证明成功了。

性质 2：划分成若干个极长上升段（长度分别为 a_1,a_2,\dots,a_w 时，含有逆序对的区间个数为 \sum_{1\le i<j \le w}a_ia_j。这个比较显然。由此我们发现，划分的连续段顺序是无所谓的。

性质 3：构造 n-a_1+1\sim n,n-a_1-a_2+1\sim n-a_1\dots 这样的序列，既可以满足划分段的条件，也可以使得其在该划分段方案中最长下降子序列最短。这个也不难证明。

至此可以直接整数划分复杂度枚举方案，可以通过本题，也可以采用更优的 dp 做法，在此不做说明。 ::::

D

::::success[正解]

（以下视 n,m,q 同阶）

一个强连通分量内的操作情况应当是相同的，所以先缩点。

此问题严格强于 DAG 可达性，因此复杂度不可能低于 O(\frac{n^2}w)，直接考虑先 bitset 求出两点可达性。

接下来考虑如何求出 u 的点权，我们可以对于每个询问找到上一个涉及 u 的 1 操作在哪，将这次操作修改成的数和此次操作之后到询问位置所有涉及 u 的 2 操作所操作的数取 gcd，就可以得到当前的点权。

于是变为两个问题：

找上一个涉及 u 的 1 操作：考虑维护每个位置上一次 1 操作的时刻，但是这个较难维护，于是将时间分块，维护到上一个整块结束时的答案，然后每次需要用到的时候在块内寻找是否有 1 操作，然后一个块结束后暴力拓扑排序 O(n) 更新即可，这部分总时间复杂度 O(nB+\frac{n^2}B)。
找一段时间区间涉及 u 的 2 操作的 gcd：同样对于时间分块，散块暴力，整块在块结尾拓扑排序更新，每次就可以直接查询，这部分总复杂度 O(n(B+\log^2 V)+\frac{n^2\log V}B)。

前面这个东西是这样的原因是，一个数不停取 gcd 只会有 \log V 次有用的更新。

（我也不知道分析的对不对，但是不会比这个大了）

然后并没有做完，因为 n^2 大小的 bitset 会爆空间，但是发现每次只需要查询某些点到块内点的可达性，于是到每个块给这个块求一个 nB 大小的 bitset 即可。

取 B=\sqrt{n\log V}，得最优时间复杂度应不超过 O(\frac{n^2}w+n\sqrt{n\log V}+n\log^2 V)。 ::::