题目链接: https://vjudge.net/contest/540876#problem/K

题意

给一个长度为 n 的数组{ai}，给 q 次问询。(1 ≤ n, q ≤ 3e5, 1 ≤ ai ≤ 1e6)

问询内容

• 1 l r 将 [l, r] 中所有元素替换为自身值的因数的数量

(如 6 会被替换成 4 ，因为6的因数为 {1,2,3,6}，总共有 4 个)

• 2 l r 输出 [l, r] 中所有元素的和

思路

首先每个数的因子数可以先用O(n)的筛子先筛出来放到一个数组里后续使用。

区间上的修改求和，考虑线段树/树状数组。由于每次修改元素的操作不符合结合律，没有办法给父节点打懒标记，直接修改单个节点的值就可以了。

这样不加思考的改点的时间复杂度大概是O(N·M·logN)，会爆掉。

考虑一个正整数 x 的因数的个数 n ，我们知道 n 的上界是 2sqrt(x)。因为因数的个数在 sqrt(x) 两边对称分布。所以对一个数 x 取其因数的操作变成 x'，有 (x'^2)/2 >= x，同理，(x''^2)/2 >= x''。由于任何大于2的数最终都会变成2(1最终会变为1)，所以一个数x能够执行的最多次数就是log2(log2(x))。对于本题的限制就是log2(log2(1e6)) = 5。

所以考虑在线段树上同时维护每个区间的和与最大值，如果这个区间的每一个数都小于等于 2 就不用再修改了。

经过优化之后的复杂度是 O(N·logN·log(log(N)))，可以接受。

代码

#include <iostream>
#include <algorithm>
#include <vector>

#define orep(i,l,r) for(auto i = (l); i < (r); ++i)
#define NL          std::cout << '\n';

const int maxN = 1e6+5;
int d[maxN];

template <typename T>
class SegTree {
  std::vector<T> tree, mx;
  std::vector<T> *arr;
  int n, root, n4, end;
  int mod;

  T range_sum(int l, int r, int cl, int cr, int p) {
    if (l <= cl && cr <= r) return tree[p];
    int m = cl + (cr - cl) / 2;
    T sum = 0;
    if (l <= m) { sum = (sum + range_sum(l, r, cl, m, p * 2)); }
    if (r > m)  { sum = (sum + range_sum(l, r, m + 1, cr, p * 2 + 1)); }
    return sum;
  }

  void range_mod(int l, int r, int cl, int cr, int p) {
    if (mx[p] <= 2) { return; }
    if (l <= cl && cr <= r && cl == cr) {
      mx[p] = tree[p] = d[tree[p]];
      return;
    }
    int m = cl + (cr - cl) / 2;
    if (l <= m) { range_mod(l, r, cl, m, p * 2); }
    if (r > m)  { range_mod(l, r, m + 1, cr, p * 2 + 1); }
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
    mx[p] = std::max(mx[p * 2], mx[p * 2 + 1]);
  }

  void build(int s, int t, int p) {
    if (s == t) {
      mx[p] = tree[p] = (*arr)[s];
      return;
    }
    int m = s + (t - s) / 2;
    build(s, m, p * 2);
    build(m + 1, t, p * 2 + 1);
    tree[p] = tree[p * 2] + tree[p * 2 + 1];
    mx[p] = std::max(mx[p * 2], mx[p * 2 + 1]);
  }

 public:
  explicit SegTree<T>(std::vector<T> v) {
    n = v.size();
    n4 = n * 4;
    tree = std::vector<T>(n4, 0);
    mx = std::vector<T>(n4, 0);
    arr = &v;
    end = n - 1;
    root = 1;
    build(0, end, 1);
    arr = nullptr;
  }

  T range_sum(int l, int r) { return range_sum(l, r, 0, end, root); }
  void range_mod(int l, int r) { range_mod(l, r, 0, end, root); }
};

int main() {
  std::ios::sync_with_stdio(0); std::cin.tie(0);
  orep(i, 1, maxN) {
    for(int j=i; j < maxN; j+=i) {
      d[j]++;
    }
  }
  int n, m; std::cin >> n >> m;
  std::vector<long long> arr(n);
  orep(i, 0, n) { std::cin >> arr[i]; }
  SegTree<long long> seg(arr);
  orep(i, 0, m) {
    int op, x, y; std::cin >> op >> x >> y;
    --x; --y;
    if (op == 1) {
      seg.range_mod(x, y);
    } else {
      std::cout << seg.range_sum(x, y); NL;
    }
  }

  return 0;
}