cf797eE. Array Queries（暴力+复杂度分析）

cf797e

还是暴力，将不同的询问根据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;
}