Nobody is needed
推销我的洛谷博客。
题意
多组数据。
给定一个长度为 \(n\) 的排列 \(a\)，你需要回答 \(q\) 组询问，每组询问给出 \(l,r\)，求有多少个子序列 \(t\) 使得：
- \(l \leqslant t_1 < t_2 < \cdots < t_k \leqslant r\)。
- \(a_{t_i} | a_{t_{i + 1}}(1 \leqslant i < k)\)。
数据范围
- \(1 \leqslant n,q \leqslant 10^6\)。
- \(a\) 是一个排列。
- \(1 \leqslant \sum n,\sum q \leqslant 10^6\)。
思路
考虑使用 dp，令 \(dp_i\) 表示以 \(a_i\) 结尾的合法子序列个数，拓扑序为 \(i\) 从小到大。
那么转移呢，很显然若是写收集形则 \(dp_i\) 可以从所有 \(a_i\) 的约数处转移过来，总复杂度是 \(O(\sum\limits_{1 \leqslant i \leqslant n}\sqrt{i})\) 的，可以用代码计算一下，当 \(n=10^6\) 时，总共需要大约 \(6 \times 10^8\)，不太能接受。
若是写扩散形，又不便于确定对于每组询问的答案。
可以考虑将拓扑序转为 \(i\) 从大到小，那么对于 \(i\)，会发生修改的 \(dp_j\) 只有那些 \(i \leqslant j\) 且 \(a_i | a_j\)，也就是说只有 \(\frac{n}{a_i}\) 处的 dp 需要修改，总复杂度为 \(O(\sum\limits_{1\leqslant i \leqslant n} \frac{n}{i})\)，很典型的调和级数 \(O(n \log n)\)，可以接受。
那么考虑怎么更新 dp 数组，正如上文所说，每次发生修改的只有 \(a_i\) 的倍数，而修改的贡献可以分为 \(a_i\) 对 \(a_i \times x(x \geqslant 2)\) 的贡献和 \(a_i \times x(x \geqslant 2)\) 对 \(a_i \times x \times y (x,y \geqslant 2)\) 的贡献，但如果 \(a_i\) 所对应的下标（即 \(i\)）在 \(a_i \times x\) 的下标后面，则无法产生贡献，\(a_i \times x\) 对 \(a_i \times x \times y\) 同理。
为了保证查询时答案没有超出 \([l,r]\) 的范围，需要在每次更新完 dp 数组后处理那些 \(l = i\) 的查询，答案就是 \(\sum\limits_{i\leqslant j \leqslant r} dp_j\)，为了快速求出答案，使用树状数组维护 dp 数组的和。
详细见代码。
复杂度
- 时间：\(O(q \log n + n \log^2 n)\)。
- 空间：\(O(n + q)\)。
Code
点击查看代码
#include <iostream>
#include <vector>
#define _1 (__int128)1
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
inline int lowbit (int x) {
return x & -x;
}
int T, n, q, a[N], b[N];
ll ans[N], tr[N], dp[N];
vector<pair<int, int>> qry[N];
void modify (int x, int y) {
for (int i = x; i <= n; i += lowbit(i)) tr[i] += y;
}
ll Query (int x) {
ll ret = 0;
for (int i = x; i; i -= lowbit(i)) ret += tr[i];
return ret;
}
void Solve () {
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i], b[a[i]] = i, tr[i] = 0, qry[i] = vector<pair<int, int>> (); // 多测要清空，b[i] 用于记录 i 在 a 中对应的下标
for (int i = 1, l, r; i <= q; i++)
cin >> l >> r, qry[l].push_back({r, i}); // 离线处理询问
for (int i = n; i; i--) {
dp[a[i]] = 1; // 初始状态
for (int j = a[i]; j <= n; j += a[i])
if (b[j] >= b[a[i]]) // 将两种转移合并可以这样写
for (int k = j * 2; k <= n; k += j) // 注意是 k += j 而不是 k += a[i]
if (b[k] > b[j])
dp[k] += dp[j];
for (int j = a[i]; j <= n; j += a[i])
modify(b[j], dp[j]), dp[j] = 0; // 用树状数组维护 dp 和，dp 要清空
for (auto [j, id] : qry[i])
ans[id] = Query(j) - Query(i - 1); // 差分处理答案
}
for (int i = 1; i <= q; i++)
cout << ans[i] << ' ';
}
int main () {
ios::sync_with_stdio(0), cin.tie(0);
// Solve();
for (cin >> T; T--; Solve(), cout << '\n') {}
return 0;
}