记录编号	585559	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[Codeforces 797E]Array Queries	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	3.027 s
提交时间	2023-12-17 14:03:30	内存使用	158.72 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 1e5+10;
int n,q,sq;
int a[N],f[N][400];
//根号分治算法 
int main(){
	freopen("arrayque.in","r",stdin);
	freopen("arrayque.out","w",stdout);
    scanf("%d",&n);
    sq = sqrt(n);
    for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
    for(int i = n;i >= 1;i--){
    	for(int j = 1;j <= sq;j++){
    		if(i + a[i] + j > n)f[i][j] = 1;
    		else f[i][j] = f[i+a[i]+j][j] + 1;
		}
	}//预处理k <= sqrt(n)的部分 
	scanf("%d",&q);
	for(int i = 1;i <= q;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		if(y <= sq)printf("%d\n",f[x][y]);
		else{
			int ans = 0;
			while(x <= n){
				x = x + a[x] + y;
				ans++;
			}//k > sqrt(n) 暴力枚举 
			printf("%d\n",ans);
		}
	}
    
    return 0;
    
}