[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})\) 复杂度，所以跑得较快些。
接下来是代码时间。
首先是离线和排序部分，应该问题不大。

1. 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);

复制代码

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

1. 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]); } } }

复制代码

1. 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; } //注意这里都要维护最大值，即最大约数

复制代码

最后就是二分求最大值。

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

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！