题解：CF1946F Nobody is needed

· · 题解

Nobody is needed

推销我的博客园。

题意

多组数据。

给定一个长度为 n 的排列 a，你需要回答 q 组询问，每组询问给出 l,r，求有多少个子序列 t 使得：

考虑使用 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 \mid 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 数组的和。

详细见代码。

复杂度

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;
}