noip20d5
A
呃？
B
朴素 dp 显然直接记录前面三个数，状态数 \(O(nm^3)\)，但是发现我们把三个数换成三个 \(\gcd\) 后缀，三者之间就一定是 \(a|b,b|c\) 的关系，状态数减小为 \(O(nm\log^2m)\)。
C
不妨设点对 \((u,v)\) 总是 \(u<v\) 的，那么对于一组询问 \((x,y)\)，答案是 \(\sum_{(a,b)\in S}\min\{|a-b|,|a-x|+|b-y|\}\)。
加入一组 \((a,b)\) 时考虑实时维护所有 \((x,y)\) 的答案，固定 \(x\)，一行 \(y\) 的变化量是 \(d_y=\min\{c,d+|b-y|\}\) 的形式，是一个绝对值函数和直线取 \(\min\) 的结果，所以就可以变成区间加一次函数，区间加常数，两次差分即可 \(O(1)\) 改一行 \(y\)。
询问的时候就对 \(x\) 的对应行前缀和即可，时间复杂度 \(O(nq)\)。
D
？？