Luogu5610 [Ynoi2013] 大学

题意： 维护序列，支持下列两个操作：

• 把区间 中所有 的倍数除以 。
• 查询区间 的和。

强制在线。

，，时限 。

---

显然，只会有 次生效的除法操作，我们使用树状数组维护区间和，这部分复杂度为 。

现在难点在于如何找到应该被除的数。

设 为序列中所有为 的倍数的数的集合， 的大小总和是 的。

当我们区间除 时，只需要在 中查看。

现在问题变为：维护一个序列，支持每次删除一个区间内的数。

使用并查集维护，对于一段已经被删除的数，可以一次跳过。

复杂度 。

极度卡常数，最好不要用 std::vector 。可以手写内存池。