求助速度问题

#include<bits/stdc++.h>

using namespace std;

int T = 0 , n = 0 , d = 0 , l = 0 , r = 0 , _ = 0;

array<int , 1000100> delta , ans , res;
array<bool , 1000100> vis;

array<vector<int> , 1000100> G;

queue<int> q;

void init()
{
	while(!q.empty()) q.pop();
	
	for(int i = 0;i < n;++ i) G[1ll * i * d % n].emplace_back(i);
	
	q.push(0);
	
	while(!q.empty())
	{
		int x = q.front() , p = 0;
		
		q.pop();
		
		delta[(x - l + 1 + n) % n] = max(delta[(x - l + 1 + n) % n] , r - l + 2);
		
		for(int i = l;i <= r;)
		{
			int nxt = (x - i + n) % n;
			
			p = delta[nxt];
			
			delta[nxt] = max(delta[nxt] , r - i + 1);
			
			if(vis[nxt]) continue;
			
			res[nxt] = ans[x];
			vis[nxt] = true;
			
			for(auto to : G[nxt])
			{
				if(ans[to] != 1e9) continue;
				
				ans[to] = ans[x] + 1;
				
				q.push(to);
			}
			
			i += p;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin >> T;
	
	while(T --)
	{
		cin >> n >> d >> l >> r >> _;
		
		for(int i = 0;i < n;++ i) vis[i] = false;
		
		for(int i = 1;i < n;++ i) ans[i] = 1e9;
		
		for(int i = 0;i < n;++ i) res[i] = 1e9;
		
		for(int i = 0;i < n;++ i) delta[i] = 1;
		
		init();
		
		while(_ --)
		{
			int pos = 0;
			
			cin >> pos;
			
			cout << (res[pos] == 1e9 ? -1 : res[pos]) << '\n';
		}
		
		for(int i = 0;i < n;++ i) G[i].clear();
	}
	
	cout << endl;
	
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int T = 0 , n = 0 , d = 0 , l = 0 , r = 0 , _ = 0 , cnt = 0;

int delta[1000100] , ans[1000100] , res[1000100];

bool vis[1000100];

struct Node{
	int to;
	int nxt;
}edge[1000100];

int head[1000100] , q[1000100];

int h = 0 , t = -1;

inline void new_line(const int a , const int b)
{
	edge[++ cnt].to = b;
	edge[cnt].nxt = head[a];
	head[a] = cnt;
	return;
}

inline void init()
{
	h = 0 , t = -1;
	
	for(int i = 0;i < n;++ i) new_line(1ll * i * d % n , i);
	
	q[++ t] = 0;
	
	while(h <= t)
	{
		int x = q[h ++];
		
		delta[(x - l + 1 + n) % n] = max(delta[(x - l + 1 + n) % n] , r - l + 2);
		
		for(int i = l , p = 0;i <= r;i += p)
		{
			int nxt = (x - i + n) % n;
			
			p = delta[nxt];
			
			delta[nxt] = max(delta[nxt] , r - i + 1);
			
			if(vis[nxt]) continue;
			
			res[nxt] = ans[x];
			vis[nxt] = true;
			
			for(int e = head[nxt];e;e = edge[e].nxt)
			{
				int to = edge[e].to;
				
				if(ans[to] != 1e9) continue;
				
				ans[to] = ans[x] + 1;
				
				q[++ t] = to;
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin >> T;
	
	while(T --)
	{
		cin >> n >> d >> l >> r >> _;
		
		cnt = 0;
		
		for(int i = 0;i < n;++ i) vis[i] = false , head[i] = 0;
		
		for(int i = 1;i < n;++ i) ans[i] = 1e9;
		
		for(int i = 0;i < n;++ i) res[i] = 1e9;
		
		for(int i = 0;i < n;++ i) delta[i] = 1;
		
		init();
		
		while(_ --)
		{
			int pos = 0;
			
			cin >> pos;
			
			cout << (res[pos] == 1e9 ? -1 : res[pos]) << '\n';
		}
	}
	
	cout << endl;
	
	return 0;
}