UOJ Logo pengyule的博客

博客

见贤思齐倍增做法注解

2023-06-06 15:53:55 By pengyule

题目链接:https://uoj.ac/contest/82/problem/806

看到赛时过的人很多都写的是倍增,之前没懂但现在懂了的我来解释一下算法的原理:

首先需要感性理解出一个事实:

f(i,j)i 过了 j 时间后的 a,则 f(i,j)=min(ai+j,max(ai,f(fai,j1)+1))

感性理解完后,再来写出

f(fai,j1)=min(afai+j1,max(afai,f(fafai,j2)+1))

把两式合并,得到

f(i,j)=min(ai+j,afai+j,max(ai,afai+1,f(fafai,j2)+2))

从此可窥见端倪:上式中的 1 代表 2j12 代表 2j,可以用倍增维护。

用倍增维护 min(... 和 max(... 即可。其中由于上界(min(...)只和查询的总时间 d 有关,所以预处理时不用预处理 +j。而最后一项,是 gd 步的终点的 a + d

一个细节需要注意!

对于两个区间 [l1,r1],[l2,r2](l1r1l2r2),依次进行复合后会变成一个长度为负数的区间,从而复合映射时会出错(你可以手动试试看)。

解决办法是,如果从后往前(由于 dp 顺序,肯定是更接近 i 的更后复合)复合到某个区间时出现了这种情况,我们就要在这种情况发生的前一个点处停止。而更前面的区间是可以完全被忽略的,这可以感性理解。

因此还需要注意不能用 gd 步的终点的 a + d 作为最后一项,而要用实际跳到的点作为终点,用它的 a + s。其中 s 为实际跳的步数。

int main(){
    n=read(),q=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)p[i]=read();
    for(int i=1;i<=n;i++){
        fa[0][i]=p[i];
        L[0][i]=R[0][i]=a[i];
    }
    for(int j=1;j<=17;j++)
        for(int i=1;i<=n;i++){
            fa[j][i]=fa[j-1][fa[j-1][i]];
            L[j][i]=max(L[j-1][i],L[j-1][fa[j-1][i]]+(1<<j-1));
            R[j][i]=min(R[j-1][i],R[j-1][fa[j-1][i]]);
        }
    for(int i=1;i<=q;i++){
        k=read(),t=read();
        int l=0,r=2e9,s=0,pp=k;
        for(int j=17;j>=0;j--)
            if(s+(1<<j)<=t)if(max(l,L[j][k]+s)<=min(r,R[j][k]+t)){
                l=max(l,L[j][k]+s),r=min(r,R[j][k]+t);
                k=fa[j][k],s+=(1<<j);
            }
        cout<<min(max(a[k]+s,l),r)<<'\n';
    }
    return 0;
}
pengyule Avatar