ABC353 | 如同流星划过天空
A. & B.
依题意模拟即可。
C.
注意只有 \(f(x,y)\) 需要对 \(10^8\) 取模，\(f\) 的求和不需要。
关注到 \(a_i \in [1,10^8)\)，故 \(a_i + a_j \in [2,2 \times 10^8)\)。
从而 \(f(x,y)=[x+y<10^8](x+y)+[x+y\ge 10^8](x+y-10^8) = x+y -10^8[x+y\ge 10^8]\)。
只需统计有序对 \((i,j)\) 使 \(a_i + a_j \ge 10^8\) 的对数即可。
枚举 \(i\)，\(j\) 的个数是在值域上一个后缀和，容易做到 \(O(n)\)。
\(\color{green}{\checkmark}\)
D.
把式子变形成 \(f(x,y)=x\times 10^{\lceil\log_{10}y\rceil}+y\)，然后拆和式即可用缀和优化。
\(\color{green}{\checkmark}\)
E.
多串 LCP 让我们想到 Trie 树。
考虑将 \(f(x,y)\) 的贡献挂在 \(y\) 上。
考虑在 Trie 树上插入的过程，每次匹配一位，我们就将在当前位失配字符串数乘上匹配长度贡献给答案即可。
\(\color{green}{\checkmark}\)
F. \(\color{#DB7D74}{\star}\)
感受那股劲。
先感受一下，曼哈顿距离是可能的答案。当 \(k=1\) 时这就是答案。
\(k>1\) 时，考虑大格子会对答案产生什么影响。
感受一下，随着 \(k\) 变大，最优方案直接穿过 \(k\times k\) 的小格子的个数断然不增。因为我们能从大格子绕路。
用一下官方题解的图：
当 \(k\) 较大时，通过左边这种方式绕路代替直接穿过是更优的。具体计算知，当 \(k=2\) 时，直接穿过更优，\(k>2\) 时，绕路更优。
那就做完了。
\(\color{green}{\checkmark}\)
G.
dp，\(f_{i,j}\) 表示已经考虑了 \([0,i)\) 的交易，目前位于 \(j\) 城市。
考虑第 \(i\) 个交易 \((T,p)\) 的转移。
首先要有 \(f_{i+1}=f_i\)，含义是原地不动。
然后是 \(f_{i+1,T}=\max\limits_{j\in[0,n)}\{f_{i,j}-|j-T|\times C\}+p\)。
把绝对值拆开，变形：\(f_{i+1,T}=\max\{\max\limits_{j\in[0,T)}\{f_{i,j} +jC\}-TC+p,\max\limits_{j\in[T,n)}\{f_{i,j}-jC\}+TC+p\}\)。
考虑用数据结构优化转移，发现我们要做的是单点修改，求前后缀最大值，开两颗 BITS 分别维护 \(f_{i,j} \pm jC\) 即可。
注意由于答案是 \(\max{f_{i,j}}\)，所以不能在 BITS 上查全局最大值作为答案，要把每次转移时计算出的 \(f_{i+1,T}\) 取最大值作为答案。
\(\color{green}{\checkmark}\)
