本场 Rating：$\textcolor{#00C0C0}{1591} \rightarrow \textcolor{#0000FF}{1668}(+77)$。
本场表现分：$\textcolor{#C0C000}{2155}$。
啊好想养一棵香香软软的线段树啊。
A Obesity
嘻嘻，没想到吧，$100^2 = 10000$。
:::success[code]
|
|
:::
B Keep the Change
无。
:::success[code]
|
|
:::
C Adjacent Sums (easy)
枚举第一位，然后依次向后算。
:::success[code]
|
|
:::
D Concentric Circles
注意到一个圆的圆心一定在其上任取两点的垂分线上。所以构成同心圆，要么是两条线不平行，要么是在同一直线上。
:::success[code]
|
|
:::
E Adjacent Sums (hard)
！？drahard？！
令每个位置的变化量为 $g_i$。
我们考虑对 $A_i + g_i + A_{i+1} + g_{i+1} \equiv B_i \pmod M$ 做变形，即：
$$g_i + g_{i+1} \equiv B_i - A_i - A_{i+1} \pmod M$$令 $C_i = B_i - A_i - A_{i+1}$，则
$$ g_i + g_{i+1} \equiv C_i \pmod M$$当确定了 $g_1$，剩下的每个数字都可以被唯一确定，即
$$g_{i+1} \equiv C_i - g_i \pmod M$$递归下去，不难发现：
奇数位是一个 $k=1$ 的一次函数，并且在 $m-g_i$ 处 $-M$；
偶数位是一个 $k=-1$ 的一次函数，并且在 $g_i$ 处 $+M$。
又因为最优解肯定 $\in [0,M)$，因此维护每一个跳变点并计算解的值。
:::success[code]
|
|
:::
F Email Scheduling Optimization
首先注意到最优解是按 $B_i$ 降序。证明？这不是板子吗。
:::info[证明（官方题解）]
Suppose that it is optimal to write to companies $P_1,P_2,\dots,P_N$, in this order.
Suppose $B_{P_i} \lt B_{P_{i+1}}$ for some $i$.
Let $S=\sum_{j=1}^{i-1}{A_{P_j}}$.
Swapping $P_i$ and $P_{i+1}$ makes the time receiving the email from company $P_i$ from $S+A_{P_i}+B_{P_i}$ to $S+A_{P_{i+1}}+A_{P_i}+B_{P_i}$,
and the time receiving the email from company $P_{i+1}$ from $S+A_{P_{i+1}}+B_{P_{i+1}}$.
$\max(S+A_{P_i}+B_{P_i},S+A_{P_i}+A_{P_{i+1}}+B_{P_{i+1}}) \ =S+A_{P_i}+A_{P_{i+1}}+B_{P_{i+1}}\ \gt \max(S+A_{P_{i+1}}+A_{P_i}+B_{P_i},S+A_{P_{i+1}}+B_{P_{i+1}}),$ so swapping them does not worsen the time required to receive all emails. We also see that, if $B_{P_i}=B_{P_{i+1}}$, then swapping $P_i$ and $P_{i+1}$ does not affect the time required. Hence, it is optimal to write emails in descending order of $B$.
:::
显然对于确定的 $A,B$ 序列，答案即 $max_{i=1}^n (\sum_{t=1}^k A_{p_t}) + B_{p_k}$。
区间最大值？
那么……
线！段！树！
但是由于 $B_i$ 可能很大，我们需要 对 998244353 取模 离散化。注意修改 $2$ 可能导致 $B$ 序列顺序变化，离散化的时候要提前留好位置。
现在考虑线段树每个节点都要维护的信息。
由于我们的计算公式，只需要维护一段区间内的元素和，以及答案。合并显然简单。
:::success[code]
|
|
:::