A
score:100/100
区间 \([i,j]\) 不合法等价于 \(s_i-s_j\le \min(p_i,p_j)\)。
将不等式拆开，对于每个 \(j\)，求出最小的满足条件的 \(i\)：
- \(s_i-p_i\le s_i\)
- \(s_i\le s_j+p_j\)
对于第一个不等式二分出合法的 \(i\) 的区间，再在这个区间上进行线段树二分维护第二个不等式。
B
scor:4/100
考虑 dp。枚举终点计算答案。
终点显然是左右横跳后再跳进来，考虑维护 \(f_{i,j}\) 为 \([1,i]\) 中有 \(j\) 个向右边跳的方案数，\(g_{i,j}\) 为后缀左跳。
按情况转移。
C
score:0/100 结论：\(1\) 为直径中点时，后手胜；否则先手胜。
则求有多少个连通图以 \(1\) 为直径中点，不难得到 \(O(n^2)\) dp。
dsu on tree 加速转移即可做到 \(O(n\log n)\)。不过我很好奇题解的 \(O(n)\) 做法。
D
score:20/100 打表或者展示注意力可以发现可以得到的二元组排序后满足:
\((x,y)\)的后继为 \((x+1,y),(x,y+1),(x+1,y+1)\) 中的一个。
枚举二元组快速 check 即可。