qoj20737 Interval MST
如何求单次答案？设 \(p_i=\max_{j=l}^{i-1}x_j,s_i=\min_{j=i+1}^{r}x_j,c_i=\min(0,x_i-p_i,s_i-x_i)\)，答案是 \(x_r-x_l+\sum_{i=l+1}^{r-1}c_i\)。
为啥？我也不知道。
线段树，对每个节点预处理出区间内每个位置的 \(p,s,c\)。查询时，把查询区间拆成 \(O(\log n)\) 个小区间。
对一个小区间 \([l,r]\)，设他前面的区间最大值为 \(P\)，后面的区间最小值为 \(S\)，贡献是 \(\sum_{i=l}^{r}\min(c_i,x_i-P,S-x_i)\)。
显然 \(P>p_i\) 的 \(i\) 是一段前缀，\(S 的 \(i\) 是一段后缀，可以二分求出这两段然后大力分讨。
若 \(i\) 只在前缀里，贡献是 \(\min(x_i-P,c_i)=x_i+\min(-P,c_i-x_i)\)，随便做。只在后缀是类似的。
若 \(i\) 同时在前缀和后缀里，贡献是 \(\min(0,x_i-P,S-x_i)\)，把值域分三段计数就行。
若 \(i\) 都不在，贡献就是 \(c_i\)，求和就行。
洛谷P17825 [COCI 2026/2027 #1] 三堆箱子 / Tri
我咋分治都不会？？？
设 f(a,b,l,r) 表示 \(a\) 堆顶上有连续、不一定有序的 \([l,r]\) 箱子，要把这些全都有序堆到 \(b\) 堆上。
当 \(l=r\) 时，直接把 \(a\) 顶上的箱子搬到 \(b\) 顶上就行。
否则，设 \(mid=\lfloor\frac{l+r}{2}\rfloor\)，直接分治！
若 \(a=b\)，先把 \([l,mid]\) 和 \((mid,r]\) 分到另外两个堆，然后 f(c,a,l,mid),f(d,a,mid+1,r)。
若 \(a\ne b\)，先把 \([l,mid]\) 分到 \(b\)，\((mid,r]\) 分到另外一个堆，然后 f(b,b,l,mid),f(c,b,mid+1,r)。
操作次数是 \(O(n\log n)\) 的，随便过。