2022杭电多校八 1005-Ironforge（二分+区间暴力）

题目链接：杭电多校8 - Virtual Judge

题目：

 样例输入：

1
5 5
7 1 6 6 14
7 2 3 2
1 2
1 4
3 5
5 1
3 1

样例输出：

Yes
No
Yes
Yes
Yes

题意：一条链，每个点上有一个数 ，每条边上有一个质数 。一开始在某个点上，有一个空背包，走到一个 点上可以把它的质因子放进背包，一条边如果背包里有那个质数就可以走。多组询问求从 x 出发能否走到 y。

分析：其实就是要我们求从每个点出发能够扩展到的最左和最右区域，对于每组询问u,v我们只需要判断v是否在u所扩展到的区域内就可以了。

我们可以先暴力求解一下每个点只向左走可以扩展到的左边界，当然这并不是最后的左边界，因为最后的左边界有可能是我们先向右扩展一段距离再向左扩展所能达到的位置。下面我来分析一下如何向左扩展，肯定不会是一点技巧没用的纯暴力。

对于一个点i，我们先判断他能否到达第i-1个点，如果不能，那么l[i]就等于i，否则就先令l[i]=l[i-1],然后再向左暴力扩展，每能到达一个位置x，就令l[i]=l[x]，怎么判断能否到达一个位置x呢？也就是说如何知道区间[x+1,i]内的数的质因子分解中是否含有w[x]呢？我们可以用一个vector p[i]存储质因子i所在的位置，然后直接对其进行二分就可以了，只需要保证在质因子p[w[x]]中存在区间[x+1,i]的数即可。由于我们向左扩展的时候利用到了前面已经更新好的左边界，所以均摊下来复杂度就是O(1)的，当左边界全部预处理好了之后我们从右向左直接暴力向左向右扩展边界求得每个数最终的左右边界，什么时候算是最终的左右边界呢？就是说某一时刻我在区间[l[i],r[i]]内的数的质因子既不包含w[r[i]]，也不包含w[l[i]-1]，这个时候我就无法继续向两端扩展了，这也就是我最后能扩展到的左右边界了。

最后再说一个技巧，就是说我们可以最后向所有的质因子vector中压入一个无穷大的数，这样做的目的是防止利用lower_bound函数进行二分时因为vector为空而导致的越界问题，加入一个数后就不会再产生这种问题。

这道题我们需要学会如何知道一个区间的数质因子分解中是否存在某个质因子，就是利用vector p[i]存储质因子i出现过的位置，如果我们从前往后进行质因子分解，那么位置的顺序自动就是拍好序的，等到我们需要判断某个质因子是否在某个区间中出现过的时候我们直接对这个质因子的vector直接二分位置即可。这个还是比较有用的，当时在考试的时候就没有想到这样的方法。

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=2e5+10;
int a[N],w[N];
vector<int>p[N];
int l[N],r[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		for(int i=1;i<=200000;i++) p[i].clear();
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		for(int i=1;i
			scanf("%d",&w[i]);
		for(int i=1;i<=n;i++)
		{
			for(int j=2;j*j<=a[i];j++)
			{
				if(a[i]%j==0)
				{
					p[j].push_back(i);
					while(a[i]%j==0) a[i]/=j;
				}
			}
			if(a[i]!=1) p[a[i]].push_back(i);
		}
		for(int i=1;i<=200000;i++) p[i].push_back(0x3f3f3f3f);//防止越界
		//处理左边界 
		l[1]=1;
		for(int i=2;i<=n;i++)
		{
			int id=*lower_bound(p[w[i-1]].begin(),p[w[i-1]].end(),i);
			if(id==i)
				l[i]=l[l[i-1]];
			else
			{
				l[i]=i;
				continue;
			}
			while(l[i]>1)
			{
				int tid=*lower_bound(p[w[l[i]-1]].begin(),p[w[l[i]-1]].end(),l[i]);
				if(tid<=i) l[i]=l[l[i]-1];
				else break;
			}
		}
		for(int i=n;i>=1;i--)
		{
			bool flag=true;
			r[i]=i;
			while(flag)
			{
				flag=false;
				//向右扩展
				while(r[i]
				{
					int tid=*lower_bound(p[w[r[i]]].begin(),p[w[r[i]]].end(),l[i]);
					if(tid==0x3f3f3f3f) break;
					if(tid<=r[i])
					{
						r[i]=r[r[i]+1];
						flag=true;
					}
					else break;
				}
				//向左扩展
				while(l[i]>1)
				{
					int tid=*lower_bound(p[w[l[i]-1]].begin(),p[w[l[i]-1]].end(),l[i]);
					if(tid==0x3f3f3f3f) break;
					if(tid<=r[i])
					{
						l[i]=l[l[i]-1];
						flag=true;
					}
					else break;
				}
			}
		}
		for(int i=1;i<=m;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			if(v>=l[u]&&v<=r[u]) puts("Yes");
			else puts("No");
		}
	}
	return 0;
}