A
考虑直接模拟，O(Q)。
B
检查数位求和后是否是 3 的倍数，记数位长度为 |s|，O(\sum \log|s|)。
C
考虑枚举每一个 -1，将四个方向的可收集到的金币累加后求最大值，这里可以使用加权并查集来维护，O(nm\log(nm))。
D
当固定要在序列 p 中使用的 K 个下标时，序列 p 具有如下性质：
对任意两条线性函数
f_i(x)=A_i x + B_i> f_j(x)=A_j x + B_j有
f_i\bigl(f_j(x)\bigr)\;>\;f_j\bigl(f_i(x)\bigr) \;\Longleftrightarrow\; \frac{A_i-1}{B_i}\;>\;\frac{A_j-1}{B_j},并且这一大小关系与 x 无关，只取决于 \tfrac{A_i-1}{B_i} 和 \tfrac{A_j-1}{B_j} 的大小。
因此，当你选定了 K 个下标要插入到 p 中时，为了让
f_{p_1}\bigl(f_{p_2}(\cdots f_{p_K}(1)\cdots)\bigr)
达到最大值，必须让
\frac{A_{p_1}-1}{B_{p_1}}
\;\ge\;
\frac{A_{p_2}-1}{B_{p_2}}
\;\ge\;
\cdots
\;\ge\;
\frac{A_{p_K}-1}{B_{p_K}}.
为简化描述，不妨预先将 (A,B) 对按
\frac{A_1-1}{B_1}\;\ge\;\frac{A_2-1}{B_2}\;\ge\;\cdots\;\ge\;\frac{A_N-1}{B_N}
排序。此时，原问题可等价地表述为：
在区间 \{1,2,\dots,N\} 中选出一个严格增序的长度为 K 的下标序列
1 \le p_1 < p_2 < \cdots < p_K \le N使得
f_{p_1}\bigl(f_{p_2}(\cdots f_{p_K}(1)\cdots)\bigr)最大。
这一问题可用下面的动态规划在 O(NK) 时间内求解：
-
定义状态
dp_{i,j} = \max_{\substack{p_{K-i},\dots,p_K \\\text{已选且} \,p_{K-i}\ge j}} f_{p_{K-i}}\bigl(f_{p_{K-i+1}}(\cdots f_{p_K}(1)\cdots)\bigr),即：在已经决定了末尾 i 个下标，且第 K\!-\!i 个下标至少为 j 的情况下，所能达到的最大函数值。
-
转移方程
考虑要不要在位置 j 上选一个下标：dp_{i,j} = \max\Bigl( dp_{i,j+1}, \;A_j \times dp_{i-1,j+1} + B_j \Bigr).- 不选 j：保持前面已经选了 i 个下标，最小下标要从 j+1 开始，值为 dp_{i,j+1}。
- 选 j：那就用一次函数 f_j，得到 A_j\cdot(dp_{i-1,j+1})+B_j。
-
边界条件
dp_{0,j} = 1 \quad(\text{相当于还没应用任何函数时，初始值为 }1). -
答案
\max_{1\le p_1<\cdots<p_K\le N} f_{p_1}\bigl(f_{p_2}(\cdots f_{p_K}(1)\cdots)\bigr) = dp_{K,1}.
因为状态数是 O(NK)，每次转移 O(1)，所以总体时间复杂度为 O(NK)。
E
下面给出一个基于“将二维曼哈顿距离和分解为横纵坐标可分离的函数，然后对一维区间分别预处理并双指针/二分”思想的实现，时间复杂度约为 O(N\log N + R_x + R_y + R_y\log R_y)。
-
可分离性：
\sum_{i=1}^N\bigl(|x-x_i|+|y-y_i|\bigr) =\underbrace{\sum_i|x-x_i|}_{F(x)} + \underbrace{\sum_i|y-y_i|}_{G(y)}. -
一维前缀和优化：对横/纵坐标分别排序并构造前缀和数组，令
\sum_{i: x_i\le x}(x-x_i) = kx - \sum_{i\le k}x_i,\quad \sum_{i: x_i> x}(x_i-x) = \bigl(\sum_{i>k}x_i\bigr) - (N-k)x,同理处理 y。
-
双重计数：先把所有可能的 G(y) 存入数组并排序；再对每个 x 计算 F(x)，用二分统计有多少个 G(y)\le D-F(x)。