题解 P3987 【我永远喜欢珂朵莉~】

可以发现一个数最多被/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用的平衡树很奇怪，在这个题里面处于很大的劣势。。。