CF797E Array Queries

CF797E Array Queries"/>

CF797E Array Queries

CF797E Array Queries

洛谷CF797E Array Queries

题目大意

给定一个长度为 n n n的序列 a a a和 q q q次询问。

每次询问给出 p , k p,k p,k，你要不停地执行操作 p ← p + a p + k p\leftarrow p+a_p+k p←p+ap​+k，知道 p > n p>n p>n为止，并输出操作的次数。

1 ≤ n , q ≤ 1 0 5 , 1 ≤ a i ≤ n , 1 ≤ p , k ≤ n 1\leq n,q\leq 10^5,1\leq a_i\leq n,1\leq p,k\leq n 1≤n,q≤105,1≤ai​≤n,1≤p,k≤n

题解

前置知识：根号分治

我们发现，操作次数不超过 n − p k \dfrac{n-p}{k} kn−p​，可以考虑根号分治。

当 k ≤ n k\leq \sqrt n k≤n ​时，设 f i , j f_{i,j} fi,j​表示 k = i , p = j k=i,p=j k=i,p=j时要跳几步才能使得 p > n p>n p>n，那么转移式为

f i , j = f i , j + a j + k + 1 f_{i,j}=f_{i,j+a_j+k}+1 fi,j​=fi,j+aj​+k​+1

当 j + a j + k > n j+a_j+k>n j+aj​+k>n时， f i , j = 1 f_{i,j}=1 fi,j​=1。

可以 O ( n n ) O(n\sqrt n) O(nn ​)处理出所有 f i , j f_{i,j} fi,j​。

当 k > n k>\sqrt n k>n ​时，操作次数不超过 n − p k ≤ n \dfrac{n-p}{k}\leq \sqrt n kn−p​≤n ​，直接 O ( n ) O(\sqrt n) O(n ​)模拟即可。

总时间复杂度为 O ( ( n + q ) n ) O((n+q)\sqrt n) O((n+q)n ​)。

code

#include<bits/stdc++.h>
using namespace std;
const int N=100000,B=320;
int n,q,ans,a[N+5],f[B+5][N+5];
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=sqrt(n);i++){for(int j=n;j>=1;j--){if(j+a[j]+i>n) f[i][j]=1;else f[i][j]=f[i][j+a[j]+i]+1;}}scanf("%d",&q);for(int i=1,p,k;i<=q;i++){scanf("%d%d",&p,&k);if(k<=sqrt(n)) printf("%d\n",f[k][p]);else{ans=0;while(p<=n){p=p+a[p]+k;++ans;}printf("%d\n",ans);}}return 0;
}