[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.l); read(q.r); q.id = i; } sort(q + 1, q + Q + 1, cmp);
然后是核心部分：右端点右移，树状数组维护所有约数。
while(i < q.r){ ++i; for(int j = 1; j * j <= a; j++)if(a%j==0){ int x = j; //now,lst分别维护最近两个位置 if(!now) now = i; else { lst = now; now = i; //ZY是值域，树状数组维护一整个值域 upd(ZY - x + 1, lst); } if(j * j == a) continue; //不重复统计 x = a / j; if(!now) now = i; else{ lst = now; now = i; upd(ZY - x + 1, lst); } } } void upd(int x,int d){ while(x<=ZY)tr=max(d,tr),x+=lowbit(x); } int query(int x){ int res=0;while(x)res=max(tr,res),x-=lowbit(x);return res; } //注意这里都要维护最大值，即最大约数
最后就是二分求最大值。
int l=1,r=ZY; while(l>1;if(query(ZY-mid+1)>=q.l)l=mid;else r=mid-1; }
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 新版吗？好像是停更了吧。 收藏一下 不知道什么时候能用到 懂技术并乐意极积无私分享的人越来越少。珍惜 鼓励转贴优秀软件安全工具和文档！ 很好很强大我过来先占个楼 待编辑 鼓励转贴优秀软件安全工具和文档！ 感谢发布原创作品，程序园因你更精彩 懂技术并乐意极积无私分享的人越来越少。珍惜 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 感谢分享，下载保存了，貌似很强大 谢谢分享，试用一下 感谢分享 谢谢分享，试用一下 yyds。多谢分享 感谢分享 东西不错很实用谢谢分享 这个有用。 感谢分享，下载保存了，貌似很强大 鼓励转贴优秀软件安全工具和文档！
页:
[1]
2