自动搬运

查看原文

来自洛谷，原作者为

	Tiger_Rory 定点爆破蓝题、紫题

搬运于2025-08-24 23:18:04，当前版本为作者最后更新于2025-07-04 23:46:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本题考查离线算法和树状数组（或线段树）维护区间，思路与代码实现综合难度应该在蓝左右。本题还有更优的做法，即分块。

题意很明显，就是求区间内任选两个数能计算出的最大 $\gcd$。那么，我们会发现，这个答案其实就是区间内出现两次及以上的最大约数。

最朴素的思路当然是直接计数了，但是在线计数的最劣复杂度是 $O(qn\sqrt{\max a_i})$，显然无法接受。那我们退而求其次，考虑将每个询问离线储存，然后分块莫队，最好实现可以做到 $O(kn\sqrt{n}\log n)$，其中 $k$ 是最大约数数量 $144$。这已经相当优秀了，但还是过不去。

其实对于一个区间而言，我们只关心一个约数最近两次出现的位置，那就几乎变成了这题的翻版，对每个区间按右端点从小到大排序，然后右端点不断右移，同时用树状数组维护一下所有约数的位置，最后二分找出最大的约数就可完成此题。时间复杂度 $O(kn\log n)$。 分块由于是 $O(n\sqrt{n})$ 复杂度，所以跑得较快些。

接下来是代码时间。

首先是离线和排序部分，应该问题不大。

bool cmp(QUES A, QUES B){
  if(A.r != B.r) return A.r < B.r;
  return A.l < B.l; 
}
for(int i = 1; i <= Q; i++){
	read(q[i].l); read(q[i].r);
	q[i].id = i; 	
}
sort(q + 1, q + Q + 1, cmp); 

然后是核心部分：右端点右移，树状数组维护所有约数。

while(i < q[t].r){
	++i;
	for(int j = 1; j * j <= a[i]; j++)if(a[i]%j==0){
		int x = j;  
		//now,lst分别维护最近两个位置 
		if(!now[x]) now[x] = i;
		else {
			lst[x] = now[x]; 
			now[x] = i; 
			//ZY是值域，树状数组维护一整个值域 
			upd(ZY - x + 1, lst[x]); 
		}
		if(j * j == a[i]) continue; //不重复统计 
		x = a[i] / j; 
		if(!now[x]) now[x] = i; 
		else{
			lst[x] = now[x]; 
			now[x] = i;
			upd(ZY - x + 1, lst[x]);  
		}
	}
}

void upd(int x,int d){
	while(x<=ZY)tr[x]=max(d,tr[x]),x+=lowbit(x); 
}  
int query(int x){
	int res=0;while(x)res=max(tr[x],res),x-=lowbit(x);return res;  
} //注意这里都要维护最大值，即最大约数

最后就是二分求最大值。

int l=1,r=ZY; 
while(l<r){
	int mid=(l+r+1)>>1;if(query(ZY-mid+1)>=q[t].l)l=mid;else r=mid-1;
}