自动搬运

查看原文

来自洛谷，原作者为

	noip 对你说再见

搬运于2025-08-24 21:55:15，当前版本为作者最后更新于2017-11-27 16:57:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

可以发现一个数最多被/log次（无视掉1和0的情况）

瓶颈在于如何找出所有该被/的数而不在于如何维护

500000以内的有最多约数的数有200个约数

然后可以用平衡树来维护

把每个i插入ai的所有约数对应的平衡树里面

每次区间[l,r]中x的倍数/x的时候

则在第x个平衡树里面把区间[l,r]截出来然后DFS这个子树

边DFS边删掉里面所有ai/x后不为x倍数的下标i

平衡树访问连续size个数的复杂度为logn+size的

总复杂度O( nd + mlog^2n ) , 空间O( nd )，d为值域内最大约数个数，即200

PS.似乎莫名其妙的被链表暴力过了。。。非常无法理解

其实类似复杂度的做法很多，平衡树做法空间和时间常数都不太好

还有很多ndlogn的做法，我只卡了一部分

因为std用的平衡树很奇怪，在这个题里面处于很大的劣势。。。