还是暴力，将不同的询问根据k分开，然后bfs，建出一棵树，然后dfs。
时间复杂度：O（能过）
稍微口胡分析一下
大概是
\(min(1,q[1])*n/1 +min(2.q[2])*n/2+min(3,q[3])*n/3+.....\)
qi表示第k=i的询问个数
因为每一种k它最多将所有的a分成k类，如果全部满了，就是n，那么显然是尽量分配给前面的使得复杂度最大。
大约是\(O(n\sqrt{n})\)级别
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<ctime>
#include<unordered_map>
#include<queue>
#include<bitset>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define eb(x) .emplace_back(x)
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll mo=1e9+7;
const int N=1e5+5;
struct node{
int p,id;
};
bool operator <(const node &a,const node& b){
return a.p<b.p;
}
vector<node> v[N];
int n,a[N],m;
node c[N];
queue<int> q;
int vis[N],ans[N],p,k,x,y,f[N];
int head[N],to[N],nex[N],tot,now;
int bz[N];
int b[N],h;
void add(int x,int y){
if (bz[x]!=now) {
head[x]=0;
bz[x]=now;
}
if (bz[y]!=now) {
head[y]=0;
bz[y]=now;
}
to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x){
for (int i=head[x];i;i=nex[i]){
int v=to[i];
f[v]=f[x]+1;
dfs(v);
}
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
scanf("%d",&n);
fo(i,1,n) scanf("%d",&a[i]);
scanf("%d",&m);
fo(i,1,m) {
scanf("%d %d",&p,&k);
v[k].push_back((node){p,i});
}
fo(id,1,n) { //
if (!v[id].size()) continue;
now=id;
tot=0;
for (node i:v[id]){
if (vis[i.p]!=id) {
vis[i.p]=id;
q.push(i.p);
}
}
while (!q.empty()) {
x=q.front(); q.pop();
y=x+a[x]+id;
if (y>n) {
add(n+1,x);
continue;
}
add(y,x);
if (vis[y]!=id) {
vis[y]=id;
q.push(y);
}
}
dfs(n+1);
for (node i:v[id]) {
ans[i.id]=f[i.p];
}
}
fo(i,1,m) printf("%d\n",ans[i]);
return 0;
}