何为分治
分治（Divide and Conquer），就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。——摘自 OI wiki
在竞赛中也很有用，但是我不会。
分治实现
根据它的定义，我们很容易就想到递归求解。
void dfs(int l, int r){if(可以直接求解){...;return;}int d = ...;// 分成两个子问题dfs(l, d);dfs(d + 1, r);
}
根据题目所求的不同而变。以及线段树的实现也是根据分治的。
例题
分治的理解还是得要例题的。
- [JSOI2015] 最大公约数
我们看到这题，\(n\le 10^5\)。DP 不行；贪心不行；那么大概率就是分治了。
对于一个区间 \([l,r]\)，我们设 \(mid=\dfrac{l+r}{2}\)。
那么如果最大的子序列就在 \([l,mid]\) 或 \([mid+1,r]\) 里，我们就直接递归到 \([l,mid]\) 或 \([mid+1,r]\) 里去。
麻烦的是横跨了 \(mid\) 的情况。
我们在