洛谷 P5398
\(n, m,a_i \le 5 \times 10^5, 3s,128MB\)
标签
莫队，根号分治，（分块？）想一想求区间逆序对都只能根号做，那这个题多半也是要根号卡过去（Ynoi 毒瘤）
考虑莫队，这里只讲从 \([l, r]\) 移动到 \([l, r + 1]\)，其他 \(3\) 种都一样。
也就是要计算有多少 \(i \in [l, r]\)，\(a_i\) 是 \(a_{r + 1}\) 的因数以及多少个 \(i\)，\(a_i\) 是 \(a_{r + 1}\)的倍数。
因为 \(n, m\) 极大，只能使用二次离线处理这个问题。转化为对于前缀 \([1, x]\)，以及查询 \([l, r]\)，有多少对 \((i, j), i \in [1, x], j \in [l, r]\) 满足 \(a_i\) 是 \(a_j\) 的倍数，多少对 \(a_j\) 是 \(a_i\) 的倍数。
对于第一种，比较简单，从小到大枚举 \(x\)，维护 \(cnt_u\) 表示是元素 \(u\) 倍数的位置数量，对于 \(a_x\) 的因子 \(p\)，都 cnt[u]++ 即可，查询直接暴力扫一遍 \([l, r]\) 即可。
第二种就困难一些，不能想第一种一样维护，因为时间复杂度是 \(O(\frac{n}{a_x})\) 的。但是这个在 \(a_x\) 较大时是可行的。于是考虑根号分治：
- \(a_x \ge B\)，按照前面的方式做即可。
- \(a_x < B\)，可以对于每种 \(val = a_x\) 做，设 \(pre_j\) 表示前 \(j\) 个数中为 \(val\) 倍数的数的个数。查询时贡献就是 \((pre_r - pre_{l - 1})\) 乘上 \([1, x]\) 中 \(val\) 的出现次数，这样就不用暴力枚举 \(j\) 了。
设 \(n, m, a_i\) 同阶，时间复杂度：\(O(n \sqrt n)\)。
想到莫队和根号分治就没有思维难度了。但是代码难度还是有（卡常）
因为此题及其卡常（我卡了几个小时），写的不好喜提 \(0pts\)。于是介绍一些卡常方式。
-
比较常规的优化，如奇偶排序，快读等。
-
枚举因数不要根号枚举，最初 \(O(V \log V)\) 预处理好。
-
设莫队时块长设置为 \(500/1000\) 左右，根号分治的阈值设在 \(40 \sim 60\) 较好（或者使用动态求最有阈值的方式，不会）。
-
不要用
vector存储询问，用数组把所有询问存下来，按 \(x\) 排序，那么 \(x\) 对应的询问是一段区间。 -
不要跟我一样蠢蠢的把莫队两个指针移动分开做（虽然比较清晰），合在一起做。
-
听说还有循环展开的神人，但是前面 \(5\) 条应该够了。