网硕互联帮助中心题目 on Luogu：[ABC438E] Heavy Buckets
前置芝士：倍增。
如果你直接去看这道题目，那么肯定会没有思路。
一共要进行
10
9
10^9
109 次操作，又要询问一些操作后任意一个水桶的水容量，这看起来根本不可实现。这时，我们可以使用一种非常神奇的思想——倍增。如下是两个状态的定义：
-
n
x
t
j
,
i
nxt_{j,i}
nxtj,i 表示从第j
j
j 个水桶进行了2
i
2^i
2i 次操作后所在的人的编号； -
s
u
m
j
,
i
sum_{j,i}
sumj,i 表示第j
j
j 个水桶进行了2
i
2^i
2i 次操作后水桶中的总水量。
显而易见，这两个数组的预处理非常容易：
n
x
t
j
,
i
=
n
x
t
n
x
t
j
,
i
−
1
,
i
−
1
nxt_{j,i}=nxt_{nxt_{j,i-1},i-1}
nxtj,i=nxtnxtj,i−1,i−1
s
u
m
j
,
i
=
s
u
m
j
,
i
−
1
+
s
u
m
n
x
t
j
,
i
−
1
i
−
1
sum_{j,i}=sum_{j,i-1}+sum_{nxt_{j,i-1}i-1}
sumj,i=sumj,i−1+sumnxtj,i−1i−1
对于初始化，
n
x
t
i
,
0
=
a
i
nxt_{i,0}=a_i
nxti,0=ai 即进行
2
0
=
1
2^0=1
20=1 次传递自然在第
a
i
a_i
ai 个人手里；
s
u
m
i
,
0
=
i
sum_{i,0}=i
sumi,0=i 即经过一次操作后第
i
i
i 个水桶只被第
i
i
i 个人加过水。
接下来要查询第
T
T
T 次操作以后第
B
B
B 个水桶的水容量，这时可以直接进行二进制跳法，从
log
2
(
10
9
)
\\log_2(10^9)
log2(109) 开始，依次进行尝试，如果可以跳，则向前跳，并加上这一次跳的水容量，并将
T
T
T 减少相应的值。最终结果即为跳过程中累计的水量和。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int a[N],nxt[N][33],sum[N][33];//记得开大一点
int query(int x,int y){
int ans=0;
for(int i=31;i>=0;i—){//从大到小跳
if(x>=(1ll<<i)){//可以跳
ans+=sum[y][i];//累计水量
y=nxt[y][i];//向前跳
x-=(1<<i);//减去这次跳的操作数
}
}
return ans;
}
void solve(){
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
nxt[i][0]=a[i];//初始化
sum[i][0]=i;
}
for(int i=1;i<=31;i++){//预处理
for(int j=1;j<=n;j++){
nxt[j][i]=nxt[nxt[j][i–1]][i–1];
sum[j][i]=sum[j][i–1]+sum[nxt[j][i–1]][i–1];
}
}
while(q—){
int t,b;
cin>>t>>b;
cout<<query(t,b)<<'\\n';//查询
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T=1;
while(T—) solve();
return 0;
}
评论前必须登录！
注册