自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 21:53:47，当前版本为作者最后更新于2023-09-28 16:35:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 原题链接

• 好久没写题解了。（指一周

看到 $n,m,V$ 都是 $10^5$ 级别，应该马上反应过来：这个数据范围可以支持我们一些很暴力的操作。

考虑对 $x \in [1,V]$，预处理出 $S_x$ 表示 $x$ 的倍数在序列中出现位置的集合。令 $d$ 代表 $[1,V]$ 中所有数因子数的最大值，显然这部分预处理的时间复杂度与 $\sum_{x}{\vert S_x \vert}$ 都是 $O(nd)$ 级别的。

枚举 $x$，令 $S_x ={p_1,p_2,\dots,p_k}$，显然对于询问 $[l,r]$，答案可以取到 $x$ 当且仅当：

• $p_1 < l$ 或者 $p_k > r$。

• $\exists i \in [1,k]$，满足 $l \leq p_i \leq r$。

发现第一个条件特别烦，又因为限制条件之间是或者的关系，考虑直接把条件拆开。换句话说，对所有询问，求出满足第一个条件前半部分与第二个条件的最大的 $x$，同理求出满足第一个条件后半部分与第二个条件的最大的 $x$，二者的 $\max$ 就是该询问的答案。

显然拆出来的两部分对称，这里以满足第一个条件前半部分为例讲解。

不妨将上述条件转化为 $O(nd)$ 个三元组 $(x,y,z)$，其含义为：所有满足 $l < x,l \leq y \leq r$ 的询问的答案与 $z$ 取 $\max$。将询问按 $l$ 排序，三元组插入到 $x+1$ 的位置，双指针枚举询问与三元组，不难发现需要实现的是单点修改与区间 $\max$ 操作，用线段树可以实现。

于是问题得到解决，时间复杂度为 $O(nd \log n)$。

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define mid ((tr[p].l+tr[p].r)>>1)
const int N=1e5+10;
int n,m,c,v[N],ans[N];
vector<int> d[N],pos[N];
vector<pair<int,int>> add[N];
struct Query
{
	int l,r,id;
}q[N];
struct node
{
	int l,r,mx;
}tr[N<<2];
inline void build(int p,int l,int r)
{
	tr[p].l=l;tr[p].r=r;tr[p].mx=0;
	if(l==r) return void();
	build(p<<1,l,mid);build(p<<1|1,mid+1,r);
}
inline void change(int p,int x,int w)
{
	if(tr[p].l==tr[p].r) return tr[p].mx=max(tr[p].mx,w),void();
	if(x<=mid) change(p<<1,x,w);else change(p<<1|1,x,w);
	tr[p].mx=max(tr[p<<1].mx,tr[p<<1|1].mx);
}
inline int query(int p,int l,int r)
{
	if(tr[p].l>=l&&tr[p].r<=r) return tr[p].mx;
	int res=0;
	if(l<=mid) res=max(res,query(p<<1,l,r));
	if(r>mid) res=max(res,query(p<<1|1,l,r));
	return res;
}
inline void solveL()
{
	for(int i=1;i<=n;i++) add[i].clear();
	for(int i=1;i<=m;i++) 
	{
		if(d[i].size()<2) continue;
		for(int j=1;j<(int)d[i].size();j++) add[d[i][0]+1].push_back(mp(d[i][j],i));
	}
	sort(q+1,q+c+1,[](Query A,Query B){return A.l<B.l;});
	build(1,1,n);
	for(int i=1,j=0;i<=c;i++)
	{
		while(j+1<=q[i].l)
		{
			++j;
			for(auto x:add[j]) change(1,x.first,x.second);
		}
		ans[q[i].id]=max(ans[q[i].id],query(1,q[i].l,q[i].r));
	}
}
inline void solveR()
{
	for(int i=1;i<=n;i++) add[i].clear();
	for(int i=1;i<=m;i++) 
	{
		if(d[i].size()<2) continue;
		reverse(d[i].begin(),d[i].end());
		for(int j=1;j<(int)d[i].size();j++) add[d[i][0]-1].push_back(mp(d[i][j],i));
	}
	sort(q+1,q+c+1,[](Query A,Query B){return A.r>B.r;});
	build(1,1,n);
	for(int i=1,j=n+1;i<=c;i++)
	{
		while(j-1>=q[i].r)
		{
			--j;
			for(auto x:add[j]) change(1,x.first,x.second);
		}
		ans[q[i].id]=max(ans[q[i].id],query(1,q[i].l,q[i].r));
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) 
	{
		scanf("%d",&v[i]);
		m=max(m,v[i]);pos[v[i]].push_back(i);
	}
	for(int i=1;i<=m;i++)
		for(int j=i;j<=m;j+=i)
			for(auto x:pos[j]) d[i].push_back(x);
	for(int i=1;i<=m;i++)
	{
		sort(d[i].begin(),d[i].end());
		d[i].erase(unique(d[i].begin(),d[i].end()),d[i].end());
	}
	scanf("%d",&c);
	for(int i=1;i<=c;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i; 
	solveL();solveR();
	for(int i=1;i<=c;i++) printf("%d\n",ans[i]);
	return 0;
}