ln001
2024-11-14 17:20:31
让这道题支持区间加。
从弱化版中得到性质，在最优的划分方案中，每个区间都是单调的。
在弱化版中，我们对前缀进行 dp 来计算答案，不可扩展。为了实现区间修改，改为对区间进行 dp。
不同寻常的，称 0 与任何数都同号。
为了更好的支持区间加，首先进行一步转化。令差分数组为 b，区间 [l, r] 单调当且仅当 b_{l + 1}, b_{l + 2} \cdots b_r 均同号。
问题转化为，在序列 b_2 到 b_n 中，标记若干数，使得序列上的极长被标记连续段均同号，最大化每个极长连续段的和的绝对值的和。其中未被标记的点为原题中某个被划分出来的区间的左端点。
更简洁的，在序列 b_2 到 b_n 中，标记若干数，若相邻两数均被标记，需保证两数同号，最大化被标记的数的绝对值的和。
两个序列显然可以合并，同时又需要支持单点修改（差分后的区间修改），直接扔到线段树里，在节点上维护左端点和右端点不同的选择方案对应的答案。
Code