T6 - 划分区间
题目链接跳转：点击跳转
一道线段树优化动态规划的题目，难度趋近于 CSP 提高组的题目和 USACO 铂金组的中等题。一眼可以看出题目是一个典型的动态规划问题，但奈何数据量太大了，O(N2)O(N^2)O(N2) 的复杂度肯定会 TLE。但无论如何都是 “车到山前必有路”，看到数据范围不用怕，先打一个暴力的动态规划再优化。
按照一位 OI 大神的说法：“所有的动态规划优化都是在基础的代码上等量代换”。
与打家劫舍等线性动态规划类似，对于本题而言，设状态的定义为 dpidp_idpi 表示对 [1,i][1, i][1,i] 这个序列划分后可得到的最大贡献。通过暴力遍历 j,(1≤j<i)j, (1 \le j < i)j,(1≤j<i)，表示将 (j,i](j, i](j,i] 归位一组。另设 A(j,i)A(j, i)A(j,i) 为区间 (j,i](j, i](j,i] 的贡献值。根据以上信息可以得到状态转移方程：
dpi=max0≤j<i(dpj+A(j,i))\large{dp_i = \max_{0 \le j<i}{(dp_j + A(j, i))}} dpi =0≤j<imax (dpj +A(j,i))
接下来就是关于 A(j,i)A(j, i)A(j,i) 的计算了。设前缀和数组 SiS_iSi 表示从区间 [1,i][1, i][1,i] 的和，那么 (j,i](j, i](j,i] 区间的和可以被表示为 S[i]−S[j]S[i] - S[j]S[i]−S[j]。根据不同的 S[i]−S[j]S[i] - S[j]S[i]−S[j]，则有以下三种情况：
1. 当 S[i]−S[j]>0S[i] - S[j] > 0S[i]−S[j]>0 时，证明该区间的和是正数，贡献为 i−ji - ji−j。
2. 当 S[i]−S[j]=0S[i] - S[j] = 0S[i]−S[j]=0 时，该区间的和为零，贡献为 000。
3. 当 S[i]−S[j]<0S[i] - S[j] < 0S[i]−S[j]<0 时，证明该区间的和是负数，贡献为 −(i−j)=j−i- (i - j) = j - i−(i−j)=j−i。
综上所述，可以写出一个暴力版本的动态规划代码：
接下来考虑优化这个动态规划，注意到每一次寻找 max\tt{max}max 都非常耗时，每一次都需要遍历一遍才能求出最大值。有没有一种方法可以快速求出某一个区间的最大值呢？答案就是线段树。线段树是一个非常好的快速求解区间最值问题的数据结构。
> 更多有关区间最值问题的学习请参考：[# 浅入线段树与区间最值问题](# 浅入线段树与区间最值问题)
综上，我们可以通过构建线段树来快速求得答案。简化三种情况可得：
因此我们构造三棵线段树，分别来维护这三个区间：
1. max0≤j<idpj\max_{0\le j < i} dp_jmax0≤j<i dpj
2. max0≤j<i(dpj−j)\max_{0\le j < i} (dp_j - j)max0≤j<i (dpj −j)
3. max0≤j<i(dpj+j)\max_{0\le j < i} (dp_j + j)max0≤j<i (dpj +j)
然而我们的线段树不能仅仅维护这个区间，因为这三个的最大值还被 A(j,i)A(j, i)A(j,i) 的三种状态所限制着，因此，我们需要找的是满足 Si−SjS_i - S_jSi −Sj 在特定条件下的最大值。这样就出现了另一个严重的问题，SiS_iSi 的值可能非常的大，因此我们需要对前缀和数组离散化一下（坐标压缩：类似于权值线段树的写法）才可以防止内存超限。
这样子对于每次寻找最大值，都可以在 O(log2N)O(\log_2N)O(log2 N) 的情况下找到。本算法的总时间复杂度也控制在了 O(N×log2N)O(N \times \log_2N)O(N×log2 N) 级别。
本题的 C++ 代码如下：
本题的 Python 代码如下（由于 Python 常数过大，因此没有办法通过这道题所有的测试点，但是代码的正确性没有问题）：
当然也可以用树状数组来写，速度可能会更快一点：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
更新日志：
Dec. 3, 2024：优化了代码的变量名，T6 增加了树状数组解法。
