技术教程 编程教程 【Note】倍增 正文

【Note】倍增

2023-06-07,

真的不会。QAQ

目录
简介
大家都见过的应用：倍增求 \(\text{LCA}\)
倍增求 \(\text{LCA}\) ，但是动态加点，但是不会 \(lct\)
例题：[ZJOI2012]灾难（DAG 上的支配树）
例题：[APIO2009] 会议中心（乱序添加元素 \(\text{DP}\) 最小字典序方案）
倍增法裸应用
例题：[NOIP2012 提高组] 开车旅行
例题：[SCOI2015]国旗计划
例题：[NOIP2012 提高组] 疫情控制
常见题型：\(\color{orange}{在串中查找给定的子序列}\)
例题：2022.9.29 模拟赛 T3 - 特殊字符串
例题：「联合省选 2021 A | B」宝石
\(ST\) 表
【模板】ST 表
例题：[SCOI2016]萌萌哒
倍增，但是不是跳链题，是变形结合律题
例题：[CTSC2011]幸福路径
例题：[NOIP2018 提高组] 保卫王国

简介

倍增法。不知道算是分治还是滴批的一种东西。这里把倍增和 \(\text{ST}\) 表放一起（\(\text{ST}\) 表本质也是倍增），原理：

    倍增原理主要是二进制拆分。\(N=\sum(bit_i\times2^i)\)；

    \(ST\) 表原理主要是区间分治/合并，即 \(2^n=2^{n-1}+2^{n-1}\)

    两者都需要满足拆分后的区间合并运算的\(\color{green}{结合律}\)。

预处理：\(\text{log2}\)

lg2[1]=0;

for (int i=2;i<=n;i++) lg2[i]=lg2[i>>1]+1;

首先是倍增。用于解决快速的\(\color{orange}{定起点}\color{pink}{定向}\)跳跃。至于如何考虑跳跃的步数，一般分为以下两种情况：

    固定某个关于步数具有单调性的值大小，具有类似二分需要满足的标准；
for (int i=lg2[/*maxstep*/];i>=0;i--)

{

	if (!check(f[x][i])) continue;

	x=f[x][i];

}
    固定步长。
//当然，也可以用上面那段的写法。

while (step) x=f[x][lowbit(step)],step^=lowbit(step);

然后是 \(\text{ST}\) 表。一般有以下两种情况：

    快速预处理合并区间信息，查找拆分为至多 \(log\) 个区间信息。//其实我不知道他要是 log 有啥具体应用（）可能就是个倍增吧。
//st 表模板：RMQ O(nlogn) - O(1)

//拆成两个可以重叠的区间，从而做到 O(1)

max[l,r]=max(f[l,lg2[r-l+1]],f[r-(1<<lg2[r-l+1])+1,lg2[r-l+1]]);

//p+lg2[r-l+1]-1=r
    对区间进行操作，类似线段树分治的最后处理，将所有区间信息下传拆分为两个子区间信息。

大家都见过的应用：倍增求 \(\text{LCA}\)

先将两个点跳到相同深度。（固定深度的跳跃）

接着，将两个点一起向上跳相同步数。

这题可以倍增做的关键在于，跳超过其到 \(\text{LCA}\) 的步数的话，两个点就会相同。

于是倍增关注的标准就是\(\color{orange}{使得跳跃步数最大，并且跳后两结点不同}\)，这样两结点的父亲就是 \(\text{LCA}\) 。

倍增求 \(\text{LCA}\) ，但是动态加点，但是不会 \(lct\)

另外倍增求 \(\text{LCA}\) 还可以用于动态加点的树（新点必须是叶节点）。

例题：[ZJOI2012]灾难（DAG 上的支配树）

杂想

这题给我一种巨大trie树的感觉（）

如果在trie上做一个查询最长且字典序最小串的话，大概可以遍历每一个孩子，找到最小并且连接最深链的？

例题：[APIO2009] 会议中心（乱序添加元素 \(\text{DP}\) 最小字典序方案）

最大不重叠覆盖线段数量，但是线段编号选择字典序最小方案。属实 nb

求数量就是傻逼题，可以线段树维护 \(\text{DP}\) 或者贪心。\(\text{DP}\) 的话就是先按线段右端点排序那个

没法通过 \(DP\) 直接标记来求字典序最小方案，因为加边的顺序并非按边的编号来加。

考虑：\(\text{DP}\) 转移时，从答案相等的可转移状态中里面找出字典序最小的。或者说，在线段树中的大小比较，以 \(\text{DP}\) 值为第一关键字，以字典序大小为第二关键字。

我们把 \(\text{DP}\) 的状态转移关系当作一棵树。那么某个节点答案的序列就是根节点到该节点的路径。

于是比较两个状态，可以转化为比较他们到 \(lca\) （开区间）路径的 min 值大小。

然后就可以倍增了。跟 灾难 那题一样，倍增可以用来做动态加叶，并且在 log 时间内完成加这个点的信息处理，吊打树剖

倍增法裸应用

注意 \(\color{orange}{定起点}\color{pink}{定向}\) 的问题。

\(\color{pink}{定向定终点，使用二分确定起点。定起点定向无\color{lightblue}{限制}，使用二分确定限制。}\)

强制定向，固定终点，比如在树上跳链，一般只能往祖先的方向跳。下面有个题说这个

例题：[NOIP2012 提高组] 开车旅行

可以用 \(set\) 或双向链表快速处理出路径。可以看出，在\(\color{orange}{确定起点}\)的情况下，\(\color{pink}{路径}\)是\(\color{pink}{确定}\)的。

对于 \(Q1\)，只有一个询问，给定了路程\(\color{lightblue}{限制}\) \(x\)，以每个点为起点跑一遍倍增即可。

对于 \(Q2\)，有多组询问，但是给定了\(\color{orange}{起点}\)和路程\(\color{lightblue}{限制}\)，直接跑倍增即可。

这题以全路程中某个点开始，两者都有可能是先手，所以得多设一维分别表示。（比如下面子序列问题，从任意点开始，起点都是确定的当前。）

设 \(f/w[i][k][0/1]([0/1])\) 表示由点 \(i\) 出发，\(A/B\) 先走，共走 \(2^k\) 步， \(A/B\) 的路程终点/路程长度。转移：

\[f[i][0][0]=nex[i][0]\ \ \ \ f[i][0][1]=nex[i][1]
\]
\[f[i][k][0]=f[f[i][k-1][0]][k-1][0\oplus[k=1]]\ \ \ \ f[i][k][1]=f[f[i][k-1][1]][k-1][1\oplus[k=1]]
\]
\[w[i][0][0][0]=dis[i][0]\ \ \ \ w[i][0][1][1]=dis[i][1]
\]
\[w[i][k][0][0]=w[i][k-1][0][0]+w[f[i][k-1][0]][k-1][0\oplus[k=1]][0]
\]
\[w[i][k][0][1]=w[i][k-1][0][1]+w[f[i][k-1][0]][k-1][0\oplus[k=1]][1]
\]
\[w[i][k][1][0]=w[i][k-1][1][0]+w[f[i][k-1][1]][k-1][1\oplus[k=1]][0]
\]
\[w[i][k][1][1]=w[i][k-1][1][1]+w[f[i][k-1][1]][k-1][1\oplus[k=1]][1]
\]

Code - [NOIP2012 提高组] 开车旅行 
#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

#define MAXN (int)(1e5+233)

int lg[MAXN];

int n;

int a[MAXN];

inline void INIT() { lg[1]=0; for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1; }

struct qwq { int x,id,pre,nex; } e[MAXN];

inline bool cmp(qwq A,qwq B) { return A.x<B.x; }

int pos[MAXN];

int ta[MAXN],tb[MAXN];

inline void dlt(int P) { int nex=e[P].nex,pre=e[P].pre; if (nex) e[nex].pre=pre; if (pre) e[pre].nex=nex; }

inline long long ABS(long long A) { return A>0?A:-A; }

int f[MAXN][19][2];

long long w[MAXN][19][2][2];

long long x0;

long long A[MAXN],B[MAXN];

inline void R(int s)

{

	int i=s,D=0; long long X=x0;

	A[s]=B[s]=0;

	for (int j=lg[n-s];j>=0;j--)

	{

		if (f[i][j][D]==0||w[i][j][D][0]+w[i][j][D][1]>X) continue;

		X-=(w[i][j][D][0]+w[i][j][D][1]);

		A[s]+=w[i][j][D][0]; B[s]+=w[i][j][D][1];

		i=f[i][j][D]; D=(j==0)?(D^1):D;

	}

}

int main()

{

	scanf("%d",&n); INIT();

	for (int i=1;i<=n;i++) scanf("%d",&a[i]),e[i]=(qwq){a[i],i,0,0};

	sort(e+1,e+n+1,cmp);

	for (int i=1;i<=n;i++) e[i].pre=i-1,e[i].nex=i+1,pos[e[i].id]=i;

	e[1].pre=e[n].nex=0;

	for (int i=1,p,pre,nex;i<n;i++)

	{

		p=pos[i];

		pre=e[p].pre; nex=e[p].nex;

		if (nex==0)

		{

			tb[i]=e[pre].id;

			ta[i]=e[e[pre].pre].id;

		}

		else if (pre==0)

		{

			tb[i]=e[nex].id;

			ta[i]=e[e[nex].nex].id;

		}

		else

		{

			if (e[p].x-e[pre].x<=e[nex].x-e[p].x) tb[i]=e[pre].id,pre=e[pre].pre;

			else tb[i]=e[nex].id,nex=e[nex].nex;

			if (nex==0) ta[i]=e[pre].id;

			else if (pre==0) ta[i]=e[nex].id;

			else ta[i]=(e[p].x-e[pre].x<=e[nex].x-e[p].x)?e[pre].id:e[nex].id;

		}

		dlt(p);

	}

	for (int i=1;i<=n;i++)

	{

		f[i][0][0]=ta[i];

		f[i][0][1]=tb[i];

		w[i][0][0][0]=ABS(a[ta[i]]-a[i]);

		w[i][0][1][1]=ABS(a[tb[i]]-a[i]);

	}

	for (int j=1;(1<<j)<=n;j++)

	{

		for (int i=1;i+(1<<j)<=n;i++)

		{

			f[i][j][0]=f[f[i][j-1][0]][j-1][j==1?1:0];

			if (f[i][j][0])

			{

				w[i][j][0][0]=w[i][j-1][0][0]+w[f[i][j-1][0]][j-1][j==1?1:0][0];

				w[i][j][0][1]=w[i][j-1][0][1]+w[f[i][j-1][0]][j-1][j==1?1:0][1];

			}

			f[i][j][1]=f[f[i][j-1][1]][j-1][j==1?0:1];

			if (f[i][j][1])

			{

				w[i][j][1][1]=w[i][j-1][1][1]+w[f[i][j-1][1]][j-1][j==1?0:1][1];

				w[i][j][1][0]=w[i][j-1][1][0]+w[f[i][j-1][1]][j-1][j==1?0:1][0];

			}

		}

	}

	scanf("%lld",&x0);

	int ansn=1; R(1);

	for (int i=2;i<=n;i++)

	{

		R(i);

		if (B[ansn]==0) { if ((B[i]==0&&a[i]>a[ansn])||B[i]!=0) ansn=i; }

		else if (B[i]==0) continue;

		else if (A[i]*B[ansn]==A[ansn]*B[i]&&a[i]>a[ansn]) ansn=i;

		else if (A[i]*B[ansn]<A[ansn]*B[i]) ansn=i;

	}

	printf("%d\n",ansn);

	int m;

	scanf("%d",&m);

	for (int i=1,s;i<=m;i++)

	{

		scanf("%d%lld",&s,&x0);

		R(s); printf("%lld %lld\n",A[s],B[s]);

	}

	return 0;

}

例题：[SCOI2015]国旗计划

先破环成链，线段按左端点排序。由于线段不相包含，右端点也会递增。

优良特性，任意定起点，方向固定（从任何一个点开始的最优路径是固定的，离散化一下可以 \(O(n)\) ？）

设 \(f_{i,k}\) 表示从第 \(i\) 个线段开始，跳 \(2^k\) 次到达的线段。倍增的边界即 编号 \(+n\)

例题：[NOIP2012 提高组] 疫情控制

有起点，有方向（贪心向根），两类路径\(\color{lightblue}{限制}\)都没有。所以二分答案。

我自己调不出来，不讲

常见题型：\(\color{orange}{在串中查找给定的子序列}\)

好像很套路。设 \(f_{i,k}\) 表示以 \(i\) 为起点，搜出来长度为 \(2^k\) 子序列的终点位置。

例题：2022.9.29 模拟赛 T3 - 特殊字符串

当一个字符串B是由a~z连续循环组成时，称他为特殊的字符串。

例如 长度M=6时 B 为 abcdef，长度M=29时 B 为 abcdefghijklmnopqrstuvwxyzabc

现在给你一个长度为N的字符串S，求最少删去多少个字符，才能找到长度为M的特殊子串。

如果钦定了某个位置的 \(a\) 作为开头，就要尽可能使得终点位置最前。

于是，状态定义和上面一样（

当然，还要预处理每个点之后最近的每个字母的位置。

\[f_[i][k]=f[p[f[i][k-1]][nex[S[f[i][k-1]]]]][k-1]
\]

最后以每个 \(a\) 开头找一遍答案即可。

例题：「联合省选 2021 A | B」宝石

给定一棵树，树上每个节点有颜色。

再给定一个无重复元素的序列。

多次询问 \(s\) 到 \(t\) 路径的以给定序列前缀为子序列的最长答案。

这同样是找子序列的问题，有固定的起点。但是如果方向变成向下，倍增将变得难以定向。

于是我们把询问拆成：正序 \(s \longrightarrow lca(s,t)\) 以及 倒序 \(t \longrightarrow lca(s,t)\)

前者跳完后，后者起点颜色将固定，但具体位置还要看怎么处理。

缝合状态：

设 \(f_{x,k}\) 表示以节点 \(x\) 为序列起点，向上扩展长度为 \(2^k\) 的子序列 最后停在的位置；

设 \(g_{x,k}\) 表示以节点 \(x\) 为倒序列起点，向上扩展长度为 \(2^k\) 的子序列 最后停在的位置。

\(f_{x,0}\) 和 \(g_{x,0}\) 都可以通过一遍 \(dfs\) 处理出来。然后常规：

\[f_{x,0}=pre_{pos_{c_x}+1}\ \ \ \ f_{x,i}=f_{{f_{x,i-1}\ \ \ },i-1}
\]
\[g_{x,0}=pre_{pos_{c_x}-1}\ \ \ \ g_{x,i}=g_{{g_{x,i-1}\ \ \ },i-1}
\]
\[pre_{pos_{c_i}}=x
\]

正序的部分就可以很好的用 -- 倍增 \(\text{1}\) -- 解决了。

\(\color{pink}{定向定终点，使用二分确定起点。}\)

倒序部分，考虑到问题的本质还是求最长的子序列，我们用二分。

只要二分了这一段的长度，就可以得到起点，然后又可以跳倍增力

其实对于 \(t\)，要找到其祖先中多个起点也要平方级，于是我们

离线这个部分的询问（

做完了。真 jb 难写

Code - 「联合省选 2021 A | B」宝石 
#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <vector>

using namespace std;

#define MAXN (int)(2e5+233)

#define MAXC (int)(2e5+233)

int book[MAXC],lg2[MAXN];

int n,m,C;

//E

struct qwq

{

	int nex,to;

}e[MAXN<<1];

int h[MAXN],tot=0;

inline void add(int x,int y)

{

	e[++tot].to=y;

	e[tot].nex=h[x];

	h[x]=tot;

}

int siz[MAXN],fa[MAXN],son[MAXN],dep[MAXN],top[MAXN];

void dfs_1(int x)

{

	siz[x]=1;

	for (int i=h[x],y;i;i=e[i].nex)

	{

		y=e[i].to;

		if (fa[x]==y) continue;

		fa[y]=x;

		dep[y]=dep[x]+1;

		dfs_1(y);

		siz[x]+=siz[y];

		if (siz[y]>siz[son[x]]) son[x]=y;

	}

}

void dfs_2(int x,int F)

{

	top[x]=F;

	if (!son[x]) return;

	dfs_2(son[x],F);

	for (int i=h[x],y;i;i=e[i].nex)

	{

		y=e[i].to;

		if (y==fa[x]||y==son[x]) continue;

		dfs_2(y,y);

	}

}

inline int lca(int x,int y)

{

	while (top[x]!=top[y])

	{

		if (dep[top[x]]<dep[top[y]]) swap(x,y);

		x=fa[top[x]];

	}

	return dep[x]<dep[y]?x:y;

}

int b[MAXN][17],c[MAXN][17];

int p[MAXC],a[MAXN],LIN[MAXC];

int stt[MAXN];

//offline

void dfs1(int x)

{

	b[x][0]=book[p[LIN[a[x]]+1]];

	c[x][0]=book[p[LIN[a[x]]-1]];

	for (int i=1;i<=lg2[dep[x]];i++)

	{

		b[x][i]=b[b[x][i-1]][i-1];

		c[x][i]=c[c[x][i-1]][i-1];

	}

	int tmp=book[a[x]];

	book[a[x]]=x;

	stt[x]=book[p[1]];

	for (int i=h[x],y;i;i=e[i].nex)

	{

		y=e[i].to;

		if (y==fa[x]) continue;

		dfs1(y);

	}

	book[a[x]]=tmp;

}

struct que

{

	int x,tp,endc,ID;

};

vector<que> v[MAXN];

int answer[MAXN];

void sol1(int x,int lca,int y,int ID)

{

	//x=stt[x] dep[stt[x]] < dep[lca] ?

	if (dep[stt[x]]<dep[lca])

	{

		v[y].push_back((que){y,lca,0,ID});

		return;

	}

	x=stt[x];

	int ed=x;

	int LG=min(lg2[dep[x]],lg2[m]);

	for (int i=LG;i>=0;i--)

	{

		if (dep[b[ed][i]]<dep[lca]) continue;

		ed=b[ed][i];

	}

	v[y].push_back((que){y,lca,a[ed],ID});

	answer[ID]=LIN[a[ed]];

}

inline bool check(int s,int tlca,int x)

{

	x-=1;

	if (dep[s]<=dep[tlca]) return false;

	while (x&&s) { s=c[s][lg2[x]]; x-=(1<<lg2[x]); }

	return dep[s]>dep[tlca];

}

inline int bina(int s,int tlca,int lasted)

{

	int l=1,r=min(dep[s],m),mid;

	bool flag=0;

	while (l<r)

	{

		mid=((l+r+1)>>1);

		if (check(book[p[LIN[lasted]+mid]],tlca,mid)) l=mid,flag=1;

		else r=mid-1;

	}

	if (flag) return l;

	bool W_=check(book[p[LIN[lasted]+1]],tlca,1);

	return W_;

}

void dfs2(int x)

{

	int tmp=book[a[x]];

	book[a[x]]=x;

	int L=v[x].size();

	for (int i=0;i<L;i++)

		answer[v[x][i].ID]+=bina(v[x][i].x,v[x][i].tp,v[x][i].endc);

	for (int i=h[x],y;i;i=e[i].nex)

	{

		y=e[i].to;

		if (y==fa[x]) continue;

		dfs2(y);

	}

	book[a[x]]=tmp;

}

int main()

{

	scanf("%d%d%d",&n,&m,&C);

	lg2[1]=0; for (int i=2;i<=n;i++) lg2[i]=lg2[i>>1]+1;

	for (int i=1;i<=C;i++) scanf("%d",&p[i]),LIN[p[i]]=i;

	for (int i=1;i<=n;i++) scanf("%d",&a[i]);

	for (int i=1,x,y;i<n;i++)

	{

		scanf("%d%d",&x,&y);

		add(x,y); add(y,x);

	}

	dep[1]=1;

	dfs_1(1);

	dfs_2(1,1);

	dfs1(1);

	int Q; int x,y,LCA;

	scanf("%d",&Q);

	for (int i=1;i<=Q;i++)

	{

		scanf("%d%d",&x,&y);

		LCA=lca(x,y);

		sol1(x,LCA,y,i);

	}

	dfs2(1);

	for (int i=1;i<=Q;i++) printf("%d\n",answer[i]);

	return 0;

	//	for (int i=1;i<=n;i++) printf("-- %d:  %d\n",i,b[i][0]);

}

\(ST\) 表

【模板】ST 表

\(O(nlogn)\ -\ O(1)\ 区间\ RMQ\) 感觉只是因为 \(max\) 运算的性质能 \(O(1)\) ？ 感觉和倍增差不多。

例题：[SCOI2016]萌萌哒

每次修改，两段等长的区间，点要一一对应连边。实际上最后要求并查集个数然后计数就可以。

注意到单个区间之间的元素不互相影响，所以也可以把这些区间拆分为 log 个区间两两连边。

设 \(f_{i,k}\) 表示以元素 \(i\) 为起点，长度为 \(2^k\) 的区间。在这些区间连边，并不会破坏我们修改的信息。

类似线段树分治，最后再下传所有的信息。枚举 \(k\)，将每层的区间并查集关系，拆成两对下层的区间并查集关系。

很喵喵！

倍增，但是不是跳链题，是变形结合律题

例题：[CTSC2011]幸福路径

跳的步数能满足精度需求即可。大概是：

可以暴力，设 \(f_{i,k}\) 表示走 \(k\) 步到达 \(i\) 点的最大收益。

\[f_{i,k}=max([j\rightarrow i]f_{j,k-1})+\rho^k w_i
\]

因为每步贡献系数不均等而且并非求和而是max所以不能矩阵之类的...对吧（）

考虑类似弗洛伊德的做法有没有比较好的性质。（但好像是用上面那个定义倍增没法转移（））

如果 \(\rho=1\) 这题其实就满足简单结合律（然而实际上 \(\rho\neq1\) 大概是为了满足答案有极限），可以直接设 \(f_{i,j,k}\) 表示 \(i\) 到 \(j\) 走了 \(2^k\) 步的最大收益。枚举断点 \(o\) 则：

\[f_{i,j,k}=max(f_{i,o,k-1}+f_{o,j,k-1})
\]

而 \(\rho<1\) 的时候满足的是变形的结合律，就变成：

\[f_{i,j,k}=max(f_{i,o,k-1}+\rho^{2^{k-1}}f_{o,j,k-1})
\]

\(O(n^3log_{1e7})\) 差不多

例题：[NOIP2018 提高组] 保卫王国

换根 \(\text{DP}\) + 变形结合律倍增，但是是区间答案的可结合性。其实这个结合律还是挺广义的。

当时转移细节写心态炸了所以没继续写，草

update：CSP-S 2022 T4 数据传输

这题 \(k=2\) 与其类似。此时题意可以转化为 每次询问一条链上选择一系列不相邻的点使得点权和最小，并且规定两端点不能选。

然后就可以列出类似保卫王国的一个状态：\(w[x][k][0/1][0/1]\) 表示 \(x\) 到其祖先长度为 \(2^k\) 的这条链上，\(x\) 选/不选，祖先选/不选的最大和。

赛后稍微写了一下，写的特别丑。还过了（

才听说有把倍增的合并 \(\text{DP}\) 写成矩阵乘的形式，比我 cv 暴力合并 6k 的码清新得多。煮啵才疏学浅没见过，马上就去学。另外我没学过 \(\text{DDP}\)，我猜原理大概就和满足结合律的 \(\text{DP}\) 合并转成矩阵乘有关。

快退役了，没时间学 \(\text{DDP}\) 乐，/dk

【Note】倍增的相关教程结束。

《【Note】倍增.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!