date: 2020-09-20 12:00~17:00

2020中国大学生程序设计竞赛（CCPC） - 网络选拔赛

题目大意：有 $n$ 次操作，每次操作往平面上加个矩形，其中矩形底边在 $x$ 轴上，每次操作后求矩形并的周长。

题解：如果你把题意从周长读成了面积 : ) 那么就会发现是裸吉如一线段树。然而事实上周长仍然可以用吉如一线段树维护。

注意到周长可分成横向和纵向两个部分。对于横向部分，答案即为 $x$ 轴有矩形覆盖的长度乘 $2$。这部分容易离散化后用并查集维护。

对于纵向部分，容易发现答案为 $\sum_{i=-\infty}^{+\infty}|a_{i}-a_{i-1}|$，其中 $a_{i}$ 表示 $i$ 位置的最大值。我们可以在线段树上维护一个区间内的答案，以及左、右端点的长度，这样这棵线段树就已经是可合并的了。

考虑使用吉如一线段树维护修改。我们还需要维护最小值，最小值数量，严格次小值。考虑一次小于严格次小值的修改，那么相当于每个最小值都往上抬了一些，这会导致周长减小。

嗯？好像有些不对。只有旁边是非最小值的最小值，才会导致答案减小。因此事实上我们需要维护的不是最小值的数量，而是最小值的段数。注意这也是很容易合并的，我们判断一下左子树的 $r$ 和右子树的 $l$ 是否同时等于最小值即可。此外还有一种情况，最左边和最右边的最小值段抬高时，只会导致周长减小一倍而不是两倍（可以画图理解一下），需要特殊处理。

时间复杂度 $\mathcal{O}(n\log n)$。

题目大意：有 $2$ 到 $n+1$ 共 $n$ 个点，点 $u$ 和点 $v$ 之间有一条权为 $\text{lcm}(u,v)$。求最小生成树。

题解：每个点都选最小的邻边，如果能连通显然代价最小。对于所有的合数，将它连到一个因子即可；大于 $2$ 的质数则连到 $2$。答案即为 $\left(\sum_{i=2}^{n+1}i\right)+\left(\sum_{i=3,i\text{ is prime}}^{n+1}i\right)$。$\text{min_25}$ 筛即可。

签到题。

题目大意：在模质数 $p$ 的意义下给出 $f(0),f(1),\cdots,f(n)$，求插值后的多项式。

题解：不妨设我们能够求出 $f(1),\cdots,f(p-1)$ 的值，那么相当于我们知道了 $f(\omega^{0}),\cdots,f(\omega^{p-2})$ 的值，而我们需要求出多项式的系数。我们可以惊喜地发现，这就是 IDFT。虽然长度不是 $2$ 的幂，但是有 Bluestein 算法帮我们解决这个问题：

$$ \begin{aligned} a_{i}&=\frac{1}{p-1}\sum_{j=0}^{p-2}\omega^{-ij}b_{j}\\ &=\frac{1}{p-1}\sum_{j=0}^{p-2}\text{pow}\left(\omega, -{i+j\choose2}+{i\choose2}+{j\choose2}\right)b_{j}\\ &=\frac{1}{p-1}\omega^{{i\choose2}}\sum_{j=0}^{p-2}\omega^{-{i+j\choose2}}\omega^{{j\choose2}}b_{j} \end{aligned} $$

这样就化为了卷积。

要求 $f(n+1),\cdots,f(p-1)$ 的值，考虑拉格朗日插值：

$$ \begin{aligned} f(t)&=\sum_{i=0}^{n}y_{i}\prod_{j=0,j\neq i}^{n}\frac{t-j}{i-j}\\ &=\sum_{i=0}^{n}\frac{t!y_{i}}{(t-n-1)!(t-i)}\cdot\frac{(-1)^{n-i}}{i!(n-i)!}\\ &=\frac{t!}{(t-n-1)!}\cdot\sum_{i=0}^{n}\frac{(-1)^{n-i}y_{i}}{i!(n-i)!(t-i)} \end{aligned} $$

同样可以用一个卷积完成。

题目大意：给出 $A,B,K,W$，求 $0\le X\le A,0\le Y\le B,X\oplus Y\le W,|X-Y|\le K$ 的方案数。

题解：唯一的难点在于 $|X-Y|\le K$。不妨设 $X<Y$，考虑 $X,Y$ 第一处不相等的位之后，若 $Y$ 的第 $i$ 位为 $j$，那么给 $Y-X$ 贡献 $j\times2^{i}$；若 $X$ 的第 $i$ 位为 $j$，那么给 $Y-X$ 贡献 $(1-j)\times2^{i}$。也就是说，我们成功使得 $Y-X$ 按位独立了。但是 $Y-X$ 可能在某一位等于 $2$，因此对于 $K$ 不能只记录一位的信息。大致可以证明当前位剩 $4$ 个以上时必然有解，因此数量可以和 $4$ 取 $\min$。