P5610 解题报告

P5610 解题报告

简要题意

一个长为 \(n\) 的非负整数序列 \(a\)，支持以下两个操作：

• 1 l r x：把区间 \([l,r]\) 中所有 \(x\) 的倍数除以 \(x\)。
• 2 l r：查询区间 \([l,r]\) 的和。

本题强制在线。

数据范围： \(1\leq n,m\leq 10^5\)，\(0\leq a_i\leq 5\times 10^5\)， \(1\leq x\leq 5\times 10^5\)，\(1\leq l\leq r\leq n\)。

时间限制：\(500\) ms。

分析

首先，我们考虑一个数至多被操作 \((\log V)\) 次，所以我们不需要关心操作部分的时间复杂度。因此我们只需要分析怎么找到需要被操作的数。

我们注意到：在 \([1,5\times 10 ^5]\) 内因数最多的个数为 \(200\)。所以我们开 \(5\times 10^5\) 个链表，然后我们就可以枚举一个数的所有因数，然后把 \(a_i\) 插入到每一个因数的链表中，我们就可以二分查找操作区间的左右端点，然后操作一个点的时候我们就判断这个点是否还是 \(x\) 的因数，如果不是，就把它删掉。删掉的操作可以使用并查集实现。询问操作就用常数最小的树状数组。

但是至此，我们还是做不了这题。我们还要做很多事情：

• 首先，我们枚举一个数的因数这部分对每一个数做是 \(O(n \sqrt n)\) 的，这并不优秀。我们考虑枚举因数，然后枚举它的倍数，这个时间复杂度是调和级数，即 \(O(n \log n)\)。

• 其次，vector 实在太慢了。我们只好自己实现链表：开一个内存池，然后数据就用指针，赋值之后就可以当普通数组用了。但是注意，这个内存池不要开太大，不然会增大常数（指针移动的时间）。

于是，我们整理思路，总结一下步骤：

• 开桶，然后预处理出每一个因数的出现次数，然后预留出每一个因数的链表空间；统计每一个数的因数个数并预留空间。

• 然后预处理每一个数的因数，然后对每一个序列中的元素插入因数。

• 在询问时，先二分出当前询问区间对应到当前链表上的区间，然后通过并查集实现访问下一项，每一次访问下一项时判断当前数是否还是当前数的倍数，不是就通过并查集删掉。