【题解】2024年中国传媒大学程序设计大赛

A 小苯的区间和疑惑

考虑区间和本质上就是一段前缀和减去另一段前缀和，因此我们尽量让这个差值尽可能大即可，那就可以直接维护“前缀和数组 $pre\_sum$ ” 的前缀最小值 $pre\_min$ 和后缀最大值 $suf\_max$ ，每个 $i$ 的答案就是 $suf\_max_i - pre\_min_i$ 。

B 小苯的三元组

考虑 $lcm(x, y) \geq max(x, y)$ ，同时 $gcd(x, y) \leq min(x, y)$
因此 $lcm(a_i, a_j) \geq a_j, gcd(a_j, a_k) \leq a_j$ ，两者要想前者大于等于后者，当且仅当取等号，即： $lcm = gcd = a_j$ 。
而
$lcm(a_i, a_j) = a_j$ ，说明 $a_i$ 是 $a_j$ 的因子。
$gcd(a_j, a_k) = a_j$ ，说明 $a_k$ 是 $a_j$ 的倍数。

因此只需要预处理出 $2 \times 10^5$ 以内所有数字的倍数个数和因子个数（这步可以调和级数 $n\cdot log(n)$ ）。
接着枚举 $a_j$ ，答案加上 $a_j$ 的因子数乘 $a_j$ 的倍数即可。

C 小红的 CUC

签到题。输出一个CUC后面随便输出啥都行，但最好别随机，否则可能会再随机出一个CUC

D 小红的矩阵构造（一）

解法1：我们首先将 $a_i=n$ 的那一行全部填成1，然后将 $b_i=0$ 的那一列全部填成0，然后将 $a_i=n-1$ 的那一行全部填成1……以此类推，最终即可填完所有。

解法2（by 炸鸡块君）：观察样例得知，当且仅当 $ai+bj>n$ 时对应位置为1，否则为0。这个性质可以推广到任意排列，因为排列也可以由样例交换某些行/列形成。

E 小红的矩阵构造（二）

签到题。我们按顺序不断复制 $2\times 2$ 的全1矩阵即可，直到最终没地方赋值了（位置越界了），如果 $k$ 还没用完则输出-1。

F 小红的子树乘积

通过启发式合并来维护子树乘积的因子数量。我们需要用map维护每个素数的幂次，然后维护最终幂次加1的乘积即为因子数量。如果超过 $k$ 了则可以直接剪枝掉，其祖先必然也是超过 $k$ 的。

G 小红的独特区间

“种类数恰好为3”的区间，即“种类数不超过3”的区间数，减去“种类数不超过2”的区间数。这两个问题都可以用双指针来解决。

H 小红的生物实验

dfs板子题。首先确定“外部区域”，这部分可以从边界部分的 '.' 字符dfs出来。然后根据题意，和“外部区域”相邻的细胞器则为细胞壁，将这些全部变成字符 '.' 即可。

小红种树（一）

求 $N$ 个等差数列第 $1$ 到 $M$ 项最大值和最小值之差求和。

alt

立刻想到若干个等差数列的最大值/最小值构成一个半平面交

可以利用单调栈求得半平面交内的优势直线。

求半平面交的时候有个trick可以避免叉积爆long long，由于查询的点都是整数，所以可以用 $x=\frac{\Delta b}{-\Delta k}$ 求得焦点的 $x$ 坐标，向下取整保留整数。 $x$ 的值就是相邻优势直线有事区间的分界点，例如上图红色和蓝色的直线，求得 $x=2$ ，所以 $[1,2]$ 红色直线更优势， $[2,M]$ 的区域蓝色以及蓝色后面斜率更高的直线更优，然后依次遍历求的所有的分界点。

接下来只考虑最大值，考虑最大值和水平数轴 $y=0$ 的差值，问题转化成求每一条直线的优势区间，假设其优势区间为 $[l,r]$ ，等差数列的首项为 $a$ ，公差为 $k$ ，则有等差数列的和 $s(x)=n\cdot a+\frac{n^2-n}{2}\cdot d$ ，这段优势区间的差值为 $s(r)-s(l-1)$ ，对于最小值，重新计算依次再减去即可。