[杭电多校8 | HDUOJ]7224.Ironforge（思维 + 数论）

题目传送门：Problem - 7224 (hdu.edu.cn)

题目 / Problem

在一条横轴上有n个点，每两个相邻的点有一条边，一共n-1条边，每个点上有一个权值a，走到一个点时就可以将某个点上的a所有质因子放入背包中，每条边有一个质数权值pri，只有当pri存在于当前背包中时才能通过这条边。

有M次询问，问能否从x走到y。

思路 / Thought

这道题容易想到用两个数组 array l 和 array r 来表示某个点向左和向右可以到达的最远位置，但是不知道怎么去处理这个最大位置。因为从某个点出发，可以左右横跳到达更远的点。

先处理出暂时不考虑向左走的情况下向右可以到达的最远位置，记作r[i]，再通过这个r[i]来更新l[i]。

如何知道当拥有[s, e]区间的所有数字的权值后能否通过边b[i]呢？因为b[i]是一个1 ~ 2e5的质数，不难想到用一个数组来保存下质数b[i]出现的所有位置，如果有一个出现在[s, e]中，说明可以通过b[i]这条边，这个可以通过二分O(logN)查询，我们把这个操作同一个函数check来表示。

最后就是如何更新l[i]和r[i]了，从左往右更新，如果i-1能到i，并且i能到i - 1（这个通过check来检查，因为此时i的左右最远距离l, r并非正确的），那么i的左右最远位置就是i-1的左右最远距位置。

如果不能到达，就进行多次左右横跳直到不能跳为止。

复杂度均摊下来是O(NlogN)。

代码 / Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 9;
int a[maxn], b[maxn];

bool check(int l, int r, vector<int>& v)
{
	int pos = lower_bound(v.begin(), v.end(), l) - v.begin();
	return pos < v.size() && v[pos] <= r;
}

void solve()
{
	int N, M;cin >> N >> M;
	for(int i = 1;i <= N; ++ i)cin >> a[i];
	for(int i = 1;i <  N; ++ i)cin >> b[i];
	
	vector<int> l(maxn, 0), r(maxn, 0), v[maxn];

	for(int i = 1;i <= N; ++ i)
	{
		int t = a[i];
		for(int j = 2;j <= t; ++ j)
		{
			if(t % j == 0)v[j].push_back(i);
			while(t % j == 0)t /= j;
		}
		if(t != 1)v[t].push_back(i);
	}
	
	for(int i = N;i >= 1; -- i)//仅考虑向右走 
	{
		r[i] = i;
		for(int j = r[i] + 1;j <= N; ++ j)
		{
			//如果i能够向右走到j，就将r[i]拓展到r[j] 
			if(check(i, r[i], v[b[j - 1]]))j = r[j], r[i] = j;
			else break;
		}
	}
	l[1] = 1;
	for(int i = 2;i <= N; ++ i)
	{
		l[i] = i;
		if(r[i - 1] >= i)//i-1能到i 
		{
			if(check(l[i], r[i], v[b[i - 1]]))l[i] = l[i - 1], r[i] = r[i - 1];
		}
		else
		{
			bool tag = true;
			while(tag)
			{
				tag = false;
				//向左 
				for(int j = l[i] - 1;j >= 1; -- j)
				{
					if(check(l[i], r[i], v[b[j]]))j = l[j], l[i] = j, tag = true;
					else break;
				}
				//向右 
				for(int j = r[i] + 1;j <= N; ++ j)
				{
					if(check(l[i], r[i], v[b[j - 1]]))j = r[j], r[i] = j, tag = true;
					else break;
				}
			}
		}
	}

	while(M --)
	{
		int x, y;cin >> x >> y;
		cout << ((l[x] <= y && y <= r[x]) ? "Yes" : "No") << '\n';
	}
}


signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int _;cin >> _;
	while(_ --)solve();
	
	return 0;
}