题目链接:https://uoj.ac/contest/82/problem/806
看到赛时过的人很多都写的是倍增,之前没懂但现在懂了的我来解释一下算法的原理:
首先需要感性理解出一个事实:
设
为 过了 时间后的 ,则
感性理解完后,再来写出
把两式合并,得到
从此可窥见端倪:上式中的
用倍增维护 min(... 和 max(... 即可。其中由于上界(min(...)只和查询的总时间 +j
。而最后一项,是
一个细节需要注意!
对于两个区间
解决办法是,如果从后往前(由于 dp 顺序,肯定是更接近
因此还需要注意不能用
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;
}