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

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用的平衡树很奇怪,在这个题里面处于很大的劣势。。。