(A.)线段求并，而且线段长度一样，乱做即可。
(B.)考虑到只有四种不同的体积且连续。
所以设(large f_{i,j,k})表示前(large i)个物品取了(large k)且(large -w_1)的和为(large j).
(large j)只要枚举到(large 3n)。
(large f_{i,j,k}=max(f_{i-1,j-(w_i-w_1),k-1},f_{i-1,j,k} ))
(C.)
分类讨论。
考虑只有(4)种情况:
(1.) (R_{mx}=Max,R_{mn}=Min)
(2.) (R_{mx}=Max,B_{mn}=Min)
(3.) (B_{mx}=Max,R_{mn}=Min)
(4.) (B_{mx}=Max,B_{mn}=Min)
其中(1.2)与(3.4)等价。
考虑(1):
其中(R)可以放任何数。(B)中的数在(B_{mx},B_{mn})之间。
排个序讨论一下。(2)情况类似。
(D.)
设(f_{i,x})为第(i)次操作后有一个人位置在(x)的最小答案。
那么
[large f_{i,x}=f_{i-1,x}+|p_i-p_{i+1}|
]
[large f_{i,p_{i-1}}=f_{i-1,x}+|x-p_{i}|
]
考虑线段树优化。
上面一个式子是个全局加。
下面一个先拆绝对值：
[large f_{i,p_{i-1}}=f_{i-1,x}+x-p_{i} (x>p_i)
]
[large f_{i,p_{i-1}}=f_{i-1,x}-x+p_{i} (x<p_i)
]
线段树上维护(f_x+x)和(f_x-x)的最大值即可，支持区间查询。