source：zr 二十联测 day19 C
题意
定义序列 \(\{a_i\}\) 的权值为序列中元素之和的绝对值。
定义一个序列的划分 \(p_1,p_2,\cdots,p_k=n\) 为将序列 \(\{a_i\}\) 划分成了 \([1,p_1],[p_1+1,p_2],\cdots,[p_k+1,n]\) 这 \(k\) 段。定义划分的权值为其划分出来的 \(k\) 个子段的权值的最小值。
\(q\) 次操作，包含单点修改 \(a_i\)、区间查询 \(a_{[l,r]}\) 的划分的最大权值。
\(n,q\le 10^6\)
分析
性质 1：划分的每一段的和一定是正负交替出现。
将两个相邻的、同号的子段合并显然不劣。
性质 2：划分的段数不超过 3。
考虑中间的任意两个相邻的子段 \(i,i+1\)，显然 \(i-1,i+2\) 的两个子段正负号不同。不妨令 \(i-1\) 子段和为正。若这两个子段的和为正，则可以跟 \(i-1\) 子段合并；若为负则跟 \(i+2\) 子段合并。
令前缀和数组为 \(s_i\)，查询区间为 \((l,r]\)。
划分段数为 1 显然。
若划分段数为 2，则我们需要求 \(\max_p \min(|s_p-s_l|,|s_r-s_p|)\)。不难发现当 \(p\) 取到 \(s_p\) 为区间最大值/最小值时最优。
若划分段数为 3，不妨设 \(s_l\le s_r\)，令划分方案为 \((l,u],(u,v],(v,r]\)。
性质 3： 存在最优解使得第一个子段（令其为 \(b_1\)）必定为正。
若其为负，则 \(u\) 取在 \(s_i\) 最小值处最优，此时划分段数为 2 显然不劣。
性质 4：划分点 \(u,v\) 必定满足 \(s_u>s_r,s_v<s_l\)。
若不满足，因为三个子段的正负号分别为正负正，则 \(s_u,s_v\) 必定有至少一个在 \([s_l,s_r]\) 内，此时划分段数为 1 更优。
根据性质 4，此时的答案转化成了 \(\min(s_u-s_l,s_r-s_v)\)（\(s_u-s_v\) 显然比这两个东西大），由于 \(u<v\)，所以此时我们可以考虑枚举分界线指针，让 \(u\) 为左区间最大值，\(v\) 为右区间最小值即可。
发现 \(\min(s_u-s_l,s_r-s_v)\) 是个单峰的东西（前者随指针右移而增大，后者随指针右移而减小），用线段树维护 \(s_i\)，在线段树上二分即可。
考虑怎么把复杂度做到一老哥。考虑在线段树上把询问区间拿出来，形成 \(O(\log n)\) 个区间，先在这些区间上面执行上述流程（实际上枚举就行），然后找到一个最优区间，在该区间内线段树上二分即可。
标签：子段,min,段数,划分,绝对值,权值,区间,ZR From： https://www.cnblogs.com/dcytrl/p/18546552