牛客多校 1
C
首先对于操作一，由于加进来的 v 一定大于等于之前存在的所有的 v，所以新加的鱼一定能吃掉同一个连通块里所有的鱼，答案即为连通块大小 - 1。使用并查集维护即可。不妨令新加进来的鱼作为连通块的根。
假设某条鱼 x 的大小为 v，\(ans_x\) 表示吃完 x 所在连通块的所有鱼的最小初始大小。那么当新加一条鱼 y 到连通块时，有 \(ans_x + sz_x - 1 \geq v_y\)，所以 \(ans_x = v_y - sz_x + 1\)。那么对于连通块内任意一点 z，它需要吃完所有鱼的最小初始大小就等于 z 到连通块的根的路径上所有点的 ans 的最大值。
那么使用带权并查集维护 \(ans_x\) 就好了，对于操作二直接查询 \(ans_x - a_x\) 就能得到答案了，其中 \(a_x\) 是 x 这点的初始权值。
D
不难发现，双方每次都会选择最大的 l 切下长度为 1 的块。那么就相当于有 m 个阶段，第 i 个阶段为 \((s_i n, s_i n, \cdots, s_i n, s_{i + 1} n, \cdots, s_m n)\)。我们需要计算每个阶段之间对 \(A(n)-B(n)\) 的贡献。
直接计算会很难表示，我们可以考虑合并成前 i 个 \(s_i n\) 同时减一，一共进行 \(s_i - s_{i + 1}\) 轮，计算每一轮的贡献之后再求和。剩下就都是公式推导了。
F
注意到循环右移若干次，\(f(p)\) 的值在模 n 意义下不变，所以直接循环右移到指定位置就好了。
G
脑电波题。注意到误差范围很大，肯定是从误差入手构造。考虑到第二个条件，我们考虑构造 2n 个点，其中 n 个点在 z=0 平面上，另外 n 个点在 z=1 平面上。接下来需要保证 z=0 平面上任意一点只和 z=1 上的 n 个点距离在误差范围内。不妨取 \(\epsilon = 0.011\)。由于第一个条件，我们肯定先要隔至少 \(\epsilon\) 距离放一个点。为了避免同层内贡献，我们把 n 个点排成 10*10 的矩阵，横向纵向每隔 \(\epsilon\) 放一个点。同层内的点最大距离为 \(\sqrt{0.011^2 + 0.011^2} \approx 0.0156\)，那么两层之间点的最大距离就是 \(\sqrt{1^2 + 0.0156^2} \approx 1.0001\) 是在误差范围内的。
H
每个人的手牌的状态只有 10 种。可以预处理出双方当前状态之后的下一步状态（对应打出牌和获得牌之后的手牌状态）。
设 \(dp(t, S)\) 表示当前还剩 t 轮结束游戏，双方手牌状态为 S 的最大期望得分，那么有 \(dp(t, S) = \max_{A, a} \min_{B, b} \{ \dfrac{1}{9} \sum_{x} \sum_{y} dp(t - 1, nxt(S)) + cost(a, b) \}\)。其中 a，b 表示双方打出的手牌，x，y 表示双方获得的手牌，cost 表示这轮的得分。
由于每轮结束后会随机得到手牌，下一步状态是很随机的，不难猜到最后每一轮的期望得分会收敛到一个值。所以上述 dp 只要做若干轮之后，用最大差值值和最小差值估计收敛后的每轮期望得分即可。
J
德扑模拟题，被卡常了。注意 vector 在较短长度时频繁 push_back 会比数组慢很多。
L
对于一个询问串 t，假设我们已经知道了其在 s 中的所有出现位置 \(p_1, p_2, \cdots, p_m\)，那么对于好区间 \([l, r]\)，需要满足类似于 \(1 \leq l \leq p_i\)，\(p_i + |t| - 1 \leq r \leq n\) 的限制。
对于 max，只需要维护前缀和 \(pre_i\) 的前缀最小值和后缀最大值，答案即为后缀最大值 - 前缀最小值。
对于 sum，为了避免算重，我们把限制按照左端点分类：\(1 \leq l \leq p_1\)，\(p_1 + 1 \leq l \leq p_2\)... 对于其中某段 i 的贡献，有 \(\sum_{l = p_i + 1}^{p_{i + 1}} \sum_{r = p_i + |t| - 1}^{n} (pre_r - pre_{l - 1})\)。
拆开式子，
维护二阶前缀和就能计算该式。现在问题是对于多个模式串，怎么在文本串中找到模式串的所有出现位置。
考虑离线，对询问串去重，建 AC 自动机。对每个模式串的结尾打上标记。对每个结点维护一个指针 up，表示从该点跳 fail 指针能跳到的最近的模式串结尾。对文本串的每一个结点都跳一遍 up 指针就能找出所有的模式串的出现位置。
注意到这样询问的复杂度是合理的，因为相同长度的模式串在文本串的同一个位置只能匹配一个，所以对于每个位置的匹配总数是等于不同长度的模式串的数量。设 \(T = \sum |t|\)，那么 不同长度的模式串的数量是 \(O(\sqrt{T})\)。所以询问的总复杂度是 \(O(n \sqrt{T})\)。
