[算法] 一些分治
普通分治
其实没啥，每次只计算跨越分治中心的区间的贡献，剩下的递归到左右两边进行分治；
时间复杂度：分治树高度为 $ \Theta (\log n) $，乘上其他操作的复杂度即可；
例题一：现在有一个 $ n $ 阶排列 $ a $，计算：
其中 $ n \leq 200000 $
题意简述：找一个给定的序列的所有子区间的最小值的和；
可以线性做，对于每一个 $ a_i $，记录其向左和向右第一个小于它的值，计算一下即可；
这里讲一下分治的做法；
其实对于这种求所有区间中符合条件的区间的题目，一般都可以分治做；
考虑跨过分治中心的区间，设分治中心为 $ mid $， 我们可以从分治中心向左维护出对于任意一个左端点 $ l $，区间 $ [l, mid] $ 的最小值并存放在一个数组 $ b $ 中；
处理完上述步骤后，我们开始从分治中心向右遍历右端点，每遍历到一个右端点 $ r $，我们发现它的所有跨过分治中心的区间的最小值有两种情况：
-
是区间 $ [mid, r] $ 中的值；
-
是 $ mid $ 左边的值；
对于第一种情况，我们每次遍历时维护一个最小值 $ mi $ 即可；
对于第二种情况，暴力做法肯定不行，那怎么办呢？
挖掘一下性质，我们发现 $ b $ 数组中的值是非严格单调递减的（因为最小值只能不变或者更小，不会变大）；
所以，我们可以每次遍历右端点时用二分查找找出 $ b $ 数组中第一个大于 $ mi $ 的位置，然后小于等于它的最小值不变，大于它的最小值变为 $ mi $；
为了避免手写二分（懒，不想写），我们可以将 $ b $ 数组 $ reverse $ 一下，然后用 $ upper \ bound $ 即可；
当然，还要维护一个前缀和（注意是 $ reverse $ 后的）；
时间复杂度：分治 + 遍历 $ \Theta(n \log n) $，二分查找 $ \Theta(\log n) $，总的 $ \Theta(n \log^2 n) $ （时间复杂度确实劣了一些）；
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
long long n;
long long a[500005];
long long b[500005], sum[500005];
long long c[500005];
long long ans;
void solve(long long l, long long r) {
if (l >= r) return;
if (r - l + 1 == 2) {
ans += min(a[l], a[r]);
return;
}
long long mid = (l + r) >> 1;
long long o = 0;
for (int i = 0; i <= mid - l; i++) b[i] = 0x3f3f3f3f;
for (long long i = mid - 1; i >= l; i--) {
o++;
b[o] = min(b[o - 1], a[i]);
}
long long cnt = 0;
for (long long i = o; i >= 1; i--) {
c[++cnt] = b[i];
}
for (long long i = 0; i <= cnt; i++) {
sum[i] = 0;
}
for (long long i = 1; i <= cnt; i++) {
sum[i] = sum[i - 1] + c[i];
}
long long mi = a[mid];
for (long long j = mid + 1; j <= r; j++) {
mi = min(mi, a[j]);
long long pos = upper_bound(c + 1, c + 1 + cnt, mi) - c;
if (pos <= cnt) ans += (cnt - pos + 1) * mi;
ans += sum[pos - 1];
}
solve(l, mid);
solve(mid, r);
}
int main() {
cin >> n;
for (long long i = 1; i <= n; i++) {
cin >> a[i];
}
solve(1, n);
for (long long i = 1; i <= n; i++) ans += a[i];
cout << ans;
return 0;
}
其实很多分治的套路是维护前缀和 + 发现性质，做的时候可以注意一下；
例题二： Luogu P4062 [Code+#1] Yazid 的新生舞会；
这题貌似题解中的主流做法是用数据结构维护高阶前缀和，这里讲一下分治做法；
还是求所有区间中符合条件的区间，可以考虑分治；
找区间中的绝对众数，我们可以借鉴一下摩尔投票法，设现在我们考虑的众数为 $ x $，将不是 $ x $ 的数看为 $ -1 $，是 $ x $ 的数看为 $ 1 $，最后判断一下整个区间的和与 $ 0 $ 的关系即可；
首先，对于一个区间 $ [l, r] $，其绝对众数是 $ [l, k] $ 的绝对众数或 $ [k + 1, r] $ 的绝对众数，其中 $ l \leq k \leq r $；
所以可以令 $ k = mid $，然后分治求解；
分治时，还是先从分治中心向左找符合条件的绝对众数以及区间和所出现的次数，向右遍历时统计一下区间和是否 $ > 0 $ 即可；
由于我们要遍历绝对众数，而绝对众数最多变化 $ \Theta (\log n) $ 次（相当于每次砍一半才能更新一次绝对众数），所以总的时间复杂度为 $ \Theta (n \log^2 n) $；
写的比较粗略，可以参考一下原题解区的题解；
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int n, ddd;
int a[1000005];
long long ans;
int pos[1000005], vis[1000005], num[1000005], cnt[1000005];
void solve(int l, int r) {
if (l == r) {
ans++;
return;
}
int mid = (l + r) >> 1;
num[0] = 0;
for (int i = mid; i >= l; i--) {
if (++cnt[a[i]] > (mid - i + 1) / 2) {
if (!pos[a[i]]) {
pos[a[i]] = ++num[0];
num[pos[a[i]]] = a[i];
}
}
}
for (int i = mid + 1; i <= r; i++) {
if (++cnt[a[i]] > (i - mid) / 2) {
if (!pos[a[i]]) {
pos[a[i]] = ++num[0];
num[pos[a[i]]] = a[i];
}
}
}
for (int i = l; i <= r; i++) {
pos[a[i]] = 0;
cnt[a[i]] = 0;
}
for (int i = 1; i <= num[0]; i++) {
int sum = r - l + 1;
int ma = sum;
int mi = sum;
cnt[sum] = 1;
for (int j = l; j < mid; j++) {
if (a[j] == num[i]) {
sum++;
} else {
sum--;
}
ma = max(ma, sum);
mi = min(mi, sum);
cnt[sum]++;
}
if (a[mid] == num[i]) {
sum++;
} else {
sum--;
}
for (int j = mi; j <= ma; j++) {
cnt[j] += cnt[j - 1];
}
for (int j = mid + 1; j <= r; j++) {
if (a[j] == num[i]) {
sum++;
} else {
sum--;
}
ans += cnt[min(sum - 1, ma)];
}
for (int j = mi; j <= ma; j++) {
cnt[j] = 0;
}
}
solve(l, mid);
solve(mid + 1, r);
}
int main() {
cin >> n >> ddd;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
solve(1, n);
cout << ans;
return 0;
}
猫树分治
实话说，我就做过一个关于这个的题，感觉和普通分治没有什么区别；
直接粘我以前写的题解了（出处）：
暴力一：每次跑一边 $ DP $；
暴力二：使用背包的合并操作，时间复杂度 $ \Theta(n^2) $ ？；
正解：猫树分治；
这玩意听着这么像数据结构，其实就是一个套路；
好像它的发明者受到了线段树分治的启发？
和普通的分治没什么区别，难的是想到分治（所以才给它起了个名字嘛）；
每次只计算跨过分治中心的区间，首先预处理出从分治中心向左和向右的每个点到终点这段区间的所有 $ 200 $ 个最优值，然后进行合并，注意要将不跨过分治中心的区间筛选出来，分别放在左右两边，然后继续递归；
所以我们需要四个指针，两个记录现在处理的序列上的左右端点，另外两个记录现在处理的问题的区间（这里的 “区间” 并不绝对，只要是没处理的，都能出现在这一段区间），然后正常递归即可；
时间复杂度：$ T(200n \log n) $；
点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, m;
int h[500005], w[500005];
struct sss{
int l, r, t;
}b[500005];
int ans[500005], p[500005], s[500005], ncnt;
int f[50005][205];
void solve(int l, int r, int L, int R) {
if (L > R) return;
int mid = (l + r) >> 1;
int Mid = L - 1;
for (int i = 0; i <= 200; i++) f[mid][i] = 0;
for (int i = mid + 1; i <= r; i++) {
for (int j = 0; j < h[i]; j++) f[i][j] = f[i - 1][j];
for (int j = h[i]; j <= 200; j++) {
f[i][j] = max(f[i - 1][j], f[i - 1][j - h[i]] + w[i]);
}
}
for (int i = h[mid]; i <= 200; i++) f[mid][i] = w[mid];
for (int i = mid - 1; i >= l; i--) {
for (int j = 0; j < h[i]; j++) f[i][j] = f[i + 1][j];
for (int j = h[i]; j <= 200; j++) {
f[i][j] = max(f[i + 1][j], f[i + 1][j - h[i]] + w[i]);
}
}
ncnt = 0;
int u = 0;
for (int i = L; i <= R; i++) {
u = p[i];
if (b[u].r <= mid) p[++Mid] = u;
else if (mid < b[u].l) s[++ncnt] = u;
else {
int ret = 0;
for (int i = 0; i <= b[u].t; i++) {
ret = max(ret, f[b[u].l][i] + f[b[u].r][b[u].t - i]);
}
ans[u] = ret;
}
}
for (int i = 1; i <= ncnt; i++) {
p[Mid + i] = s[i];
}
R = ncnt + Mid;
solve(l, mid, L, Mid);
solve(mid + 1, r, Mid + 1, R);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (register int i = 1; i <= n; i++) {
cin >> h[i];
}
for (register int i = 1; i <= n; i++) {
cin >> w[i];
}
for (register int i = 1; i <= m; i++) {
cin >> b[i].l >> b[i].r >> b[i].t;
if (b[i].l == b[i].r) {
if (b[i].t >= h[b[i].l]) ans[i] = w[b[i].l];
} else {
p[++ncnt] = i;
}
}
solve(1, n, 1, ncnt);
for (int i = 1; i <= m; i++) {
cout << ans[i] << endl;
}
return 0;
}
线段树分治
在区间上的操作，线段树好像都能干，并且它长得就很能分治，所以用它也并不奇怪；
看见这种在时间线上的题，一般好像可以用线段树分治来做；
以前好像还有一道，但是忘了；
首先判断二分图，我们使用可撤销的扩展域并查集，具体可以看看原题解区；
具体的，我们对于这一条时间线开一个线段树，每个节点开一个动态数组存这个点所管辖的时间段内所加边的下标，最后从根开始 $ dfs $ 一下即可；
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
int n, m, k;
stack<pair<int, pair<int, int> > > s;
int fa[500005];
int u[500005], t[500005];
int siz[500005];
int find(int x) {
return (x == fa[x]) ? x : find(fa[x]);
}
namespace seg{
inline int ls(int x) {
return x << 1;
}
inline int rs(int x) {
return x << 1 | 1;
}
struct sss{
int l, r;
vector<int> v;
}tr[500005];
void bt(int id, int l, int r) {
tr[id].l = l;
tr[id].r = r;
if (l == r) {
return;
}
int mid = (l + r) >> 1;
bt(ls(id), l, mid);
bt(rs(id), mid + 1, r);
}
void add(int id, int l, int r, int d) {
if (tr[id].l >= l && tr[id].r <= r) {
tr[id].v.push_back(d);
return;
}
int mid = (tr[id].l + tr[id].r) >> 1;
if (l <= mid) add(ls(id), l, r, d);
if (r > mid) add(rs(id), l, r, d);
}
}
void merge(int x, int y) {
if (x == y) return;
if (siz[x] > siz[y]) swap(x, y);
s.push({y, {siz[x], x}});
fa[x] = y;
siz[y] += siz[x];
}
void dfs(int id) {
bool vis = true;
int o = s.size();
for (int i = 0; i < seg::tr[id].v.size(); i++) {
int x = seg::tr[id].v[i];
int uu = find(u[x]);
int tt = find(t[x]);
if (uu == tt) {
for (int j = seg::tr[id].l; j <= seg::tr[id].r; j++) cout << "No" << endl;
vis = false;
break;
}
merge(find(u[x] + n), tt);
merge(find(t[x] + n), uu);
}
if (vis) {
if (seg::tr[id].l == seg::tr[id].r) {
cout << "Yes" << endl;
} else {
dfs(seg::ls(id));
dfs(seg::rs(id));
}
}
while(s.size() > o) {
siz[s.top().first] -= s.top().second.first;
fa[s.top().second.second] = s.top().second.second;
s.pop();
}
}
int main() {
cin >> n >> m >> k;
seg::bt(1, 1, k);
int l, r;
for (int i = 1; i <= m; i++) {
cin >> u[i] >> t[i] >> l >> r;
if (l != r) {
seg::add(1, l + 1, r, i);
}
}
for (int i = 1; i <= 2 * n; i++) {
fa[i] = i;
siz[i] = 1;
}
dfs(1);
return 0;
}
可能以后看见了新的套路等等还会再来补充；