牛客练习赛 85 D

感觉就很生草。

提供两种解法，分别是线段树套 bitset 的 和 。

考场上开场开了 D ，第一反应就是分块套 bitset ，算了算时间复杂度肯定爆了，就弃掉了，旁边的同学打了后直接 T 掉。

想了一会儿想到了以前做 Ynoi 时写过一道线段树套线性基的题，就随口说了句是不是可以线段树套 bitset 啊，同学听了后觉得很妙于是一打就过了……

其实就是对于每个数维护一下它包含了哪些质因子，在 以内质数个数数量级在 左右，所以我们考虑用一个长为 的 bitset 来记录每个质因子是否出现，因为信息的合并性比较弱所以可以不分块，用线段树维护一个区间的 bitset 即可。

修改时单点修改，单次时间复杂度 。

查询时就直接合并线段树上 个节点的 bitset ，时间复杂度 。

综上时间复杂度为 ，由于 大约是 所以总的时间复杂度其实可以类比 ，标准 时间复杂度可以过。

带修莫队我刚开始以为卡满只能 转移所以果断弃了，后来经同学提醒才发现貌似没有这么复杂。

我们可以离线，把所有的修改操作和原序列的数的质因数分解情况保存下来，然后转移的时候直接来个 cnt 数组记录每个质因数的出现次数就好了。

你刚开始看这个玩意儿好像还是 转移，但是事实上我们转移的时候可以直接把相同的质因子合并了再记录一下它们的出现次数，这样转移的时间复杂度就是质因子种类个数，由于 已经超过 了，所以一次转移至多有 个质因子，于是大概就可以控制时间复杂度为 。

吐槽一下出题人，标程放了个 bitset ，个人认为此题标程理应放莫队……。

其实一想到 bitset 这道题就差不多了（