目录
给个正常的题解以正视听 . 不过说好的普及难度呢？
如果有问题请指出 .
T2
注意到答案一定可以取到最小区间的长度 \(len\)，一种方案是按 \(0\dots len-1\) 循环填 .
T3
大致有两种做法：
- 维护每个手指的次数 \(c_i\) 和占用的键数 \(t_i\)，按 \(\frac{c_i}{t_i+1}\) 排序放堆里每次取最优的拿出来 .
- 二分答案 \(t\)，每次判断 \(\frac{c_i}t\) 之和能否达到总键数 .
T4
排序后把 \(a_{2\dots n-1}\) 与 \(a_1,a_n\) 中最远的那个连边，然后连 \(a_1-a_n\) 即可 .
正确性可以考虑 Boruvka 算法的流程，先连 \(a_{2\dots n}\) 就是这个结果，最后剩两个连通块肯定是 \(a_1,a_n\) 连 .
T5
令 \(dp_{l,r}\) 表示区间 \([l,r]\) 的答案，转移有以下几种：
- 如果 \(s_l,s_r\) 是匹配的括号，则 \(dp_{l,r}\overset{\min}\gets dp_{l+1,r-1}\) .
- 对左边或者右边加一个括号构成匹配，\(dp_{l,r}\overset{\min}\gets\min\{dp_{l+2,r},dp_{l,r-2}\}+1\) .
- 拆成两部分的答案拼起来，\(dp_{l,r}\overset{\min}\gets\min\limits_k\{dp_{l,k}+dp_{k+1,r}\}\) .
具体就是按照合法括号序列的构成转移 . 时间复杂度 \(\Theta(n^3)\) .
T6
线段树维护历史版本和，可以看吉司机论文 .
写一个看到的最简单的做法，线段树维护向量 \([hsum\quad sum\quad1]^{\mathsf T}\) 表示历史和、和、1 . 对于一次区间加 \(v\) 可以表示为矩阵乘法：
\[\begin{bmatrix}hsum'\\sum'\\1\end{bmatrix}=\begin{bmatrix}hsum\\sum\\1\end{bmatrix}\begin{bmatrix}1&1&v\\0&1&v\\0&0&1\end{bmatrix} \]可能需要卡常，我不知道 . 时间复杂度 \(O(n+q\log n)\) .
T7
考虑横着差分一次，那么就变成一个竖线加一个数，一条斜线减一个数 . 对每列每个对角线开一个树状数组分别维护即可 .
时间复杂度 \(\Theta(n^2+q\log n)\) .
APJ 之言可谓是切中了
红 - 绿 - 橙 + 蓝 .