真的不会。QAQ
目录简介
倍增法。不知道算是分治还是滴批的一种东西。这里把倍增和 \(\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}\) + 变形结合律倍增,但是是区间答案的可结合性。其实这个结合律还是挺广义的。
标签:倍增,int,text,Note,color,MAXN,例题 From: https://www.cnblogs.com/Kan-kiz/p/16822483.html