分治
序列分治
通常是用来处理子段的问题:
比如,给定一个长度为
直接枚举左右端点就是
把所有子数组按它跨过的区域中,分治层级中最高一级的下标分类
比如一段区间
另一个段区间
在分治结构上,会处理掉对应着这一层级的答案。
比如在分治结构上,
这些区间的共同特点就是,在
(换句话说,左端点在
基本分治函数:
void solve(int l,int r)
{
if(l==r)
{
//长度为一的时候直接处理一下。
return;
}
int mid=(l+r)/2;
solve(l,mid);solve(mid+1,r);
//统计跨过了(mid,mid+1) ,且范围在 l~r 之间的子区间的答案。
}
2
3
4
5
6
7
8
9
10
11
然后如何统计答案:
先来个简单的:求所有子区间数字之和。
设当前分治到的范围是
设数组
设数组
然后枚举左端点在哪:
void solve(int l,int r)
{
if(l==r)
{
//长度为一的时候直接处理一下。
ans+=a[l];
return;
}
int mid=(l+r)/2;
solve(l,mid);solve(mid+1,r);
//统计跨过了(mid,mid+1) ,且范围在 l~r 之间的子区间的答案。
//左端点到中间点的答案是 pre[i]
//右端点可以取 mid+1 ~ r 之间的所有值。
//所以答案是 (pre[i]+suf[mid+1])+……+(pre[i]+suf[r])
//上面的式子经过预处理,可以O(1) 算出来
pre[mid+1]=suf[mid]=0;
int ss=0;
for(int i=mid+1;i<=r;++i) suf[i]=suf[i-1]+a[i],ss+=suf[i];
for(int i=mid;i>=l;--i)
{
pre[i]=pre[i+1]+a[i];
ans+=pre[i]*(r-(mid+1)+1)+ss;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
再来个难点的:求所有子区间的最大公约数之和。
还是分治到的区间是
最大公约数每次变化,就会减少一个质因子,而质因子最少为
也就是,一个序列的前缀的最大公因数最多有
可以预处理右半边序列的最大公因数有多少种。
void solve(int l,int r)
{
if(l==r)
{
//长度为一的时候直接处理一下。
ans+=a[l];
return;
}
int mid=(l+r)/2;
solve(l,mid);solve(mid+1,r);
//设 g 是 a[i] ~ [mid] 的最大公约数。
//右端点还是可以取 mid+1 ~ r 之间的所有值。
//但是这次 gcd 不是单纯的加法,不好化成 O(1)
//先取 g 和 a[mid+1] 的 gcd 的值是多少,设为 g', 然后二分满足区间 gcd = g' 的最靠右的位置在哪。
//这样每次 gcd 都会变化,gcd 最多变 log 次就会变成 1 了。
//所以总复杂度是 O(len*log*log)。
gr[mid+1]=a[mid+1];
for(int i=mid+2;i<=r;++i) gr[i]=gcd(gr[i-1],a[i]);
for(int i=r;i>=mid+1;--i)
{
//nxt[i] 表示下一个不和自己相同的位置在哪
if(i==r||gr[i]!=gr[i+1]) nxt[i]=i+1;
else nxt[i]=nxt[i+1];
}
for(int i=mid;i>=1;--i)
{
if(i==mid) g=a[mid];
else g=gcd(a[i],g);
int pos=mid+1;
while(pos<=n)
{
ans+=gcd(gr[pos],g)*(nxt[pos]-pos);
pos=nxt[pos];
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
还有其他类型,虽然没有明说是区间问题,但其实也是:
比如求一个序列的逆序对数。
实际上我们可以枚举每一对
那么可以看作是对于每一个区间,判断左端点是否大于右端点。
分治的时间复杂度:
每一次把区间分成两段,那么分
每一段区间,复杂度和区间长度有关系,如果区间长度是
一共