这个分治策略其实跟整体二分差不多，但是它的应用面比较单一和具有针对性。
通常是 \(dp_1,dp_2,dp_3,...,dp_n\) 只有 \(O(d)\) 段。然后我们通过分治来看 \(dp_i=v\) 的应该是哪一段。
def solve(l,r)
if dp(l)==dp(r)
fill dp(l+1),dp(l+2),...,dp(r-1) with dp(l)
return
mid := l+r>>1
calc dp(mid)
solve(l,mid)
solve(mid,r)
有时，这个 \(d\) 比较小，从而分治的复杂度就是 \(O(d\log T)\) 的，其中 \(T\) 为暴力计算一处 \(dp\) 值的复杂度，比如 USACO23Feb Watching Cowflix。
有时，这个 \(d\) 比较大，比如 CF1693D Decinc Dividing，但是可以 \(O(段长)\) 计算一个连续段中的某处的 \(dp\) 值，从而同一层的总复杂度是 \(O(\sum 段长)=O(n)\) 的，总共就是 \(O(n\log n)\)。
还有时，它满足其他优秀的性质，从而使得复杂度仍然是 \(polylog\) 的。
当你发现计算一处 dp 值非常容易，却苦于对于每一处都计算 dp 值的低效时，你可以尝试这种分治策略。
当你发现 dp 值具有单调性时，你也可以往这方面想想，因为如果这些连续段的 dp 值不单调也很难满足一些很好的性质。（你看，上面两道题都是单调的。）
给定一个排列 \(\{p_n\}(n\le 2\times 10^5)\)，问有多少个子段可以被划分成一个上升子序列和一个下降子序列（可为空）。
暴力判断一个长为 \(len\) 的序列是否可以被划分为 IS 和 DS 的并就是一个 NOIP 模拟赛的套路。设 \(f_i\) 表示到了 \(i\) 处将 \(i\) 选进 DS，IS 的最小末尾值，以及选进 IS，DS 最大末位置 \(g_i\)，即可简单转移。复杂度 \(O(len)\)。
运用上文的分治做法即可得到 \(O(n\log n)\) 复杂度，原因就是上面的第二个“有时”。
法2：
【套路1】判断一个数列 \(p\) 是否能够划分成 一个上升子序列 和 一个下降子序列 的并，只需判断是否存在 \(4\) 个元素 \(a<b<c<d\)，使得 \(p_b>p_a>p_d>p_c\) 或 \(p_b<p_a<p_d<p_c\)。
【套路2】如何统计包含【套路1】中四元组的子段的数量？经典数形状问题。先把 \(p_b>p_a\) 的二元组找到，把 \(p_b\) 对应的最大的 \(p_a\) 记作 \(h_b\)，然后枚举 \(b\)，判断所有 \(d>b,p_d<h_b\) 且 \(d\) 已被 activate 的 \(d\) 数量，然后用 \(p_{b+1}\) 作为 \(p_c\) 去 activate 所有没有被 activate 的 \(d,p_d>p_{b+1}\)，然后将其从 set 中删除。
法3：
【套路3】对于一处 \(i\)，\(f_i,g_i\) 均只有 \(4\) 种可能的取值。
利用这个性质，用记忆化来优化暴力的枚举左端点再往右计算 dp 值的 \(O(n^2)\) 做法即可做到 \(O(n)\)。
具体来说，枚举一个左端点 \(l\)，设 \(O(n-l)\) 计算一次暴力 dp 的 dp 数组为 \(F(l,i)\)，则对于一处 \(i\)，如果发现 \(F(l,i)=F(l+1,i)\) 且 \(G(l,i)=G(l+1,i)\)，则更大的 \(i\) 也是跟上一轮一样的，不用继续了，直接沿用上一轮的结论即可。否则，从 \(i\) 的视角考虑 \(F(l,i)\ne F(l+1,i)\) 的 \(l\) 的个数，很明显只会有 \(7\) 种（因为不可能来回地边，这个关于 \(l\) 也是单调的啊）。于是就线性了。