题解：P12786 [ICPC 2024 Yokohama R] Greatest of the Greatest Common Divisors

· · 题解

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

题意很明显，就是求区间内任选两个数能计算出的最大 \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;
}