数学题

题目背景
你喜欢数学吗！（反正我不喜欢）
不管你喜不喜欢！这是一道数学题！
题目描述
定义一个函数d(x)为x的约数个数。例如，d(4) = 3,d(12) = 6。
有n个数a1,a2,...,an，对它们进行两种操作：
1 l r：对所有i∈[l,r]，将ai变成d(ai)。
2 l r：输出[l,r]的区间和。
输入输出格式
输入格式
第一行两个整数n和m，分别表示序列a的长度和操作次数。
第二行n个整数，表示序列a的初值。
接下来m行每行三个整数表示操作，格式见“题目描述”。
输出格式
对于每个操作2，输出一行答案。

  1 #include <cstdio>
  2 #include <cmath>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <map>
  7 #define space putchar(' ')
  8 #define enter putchar('
')
  9 typedef long long ll;
 10 using namespace std;
 11 template <class T>
 12 void read(T &x){    //读入优化啊 
 13     char c;
 14     bool op = 0;
 15     while(c = getchar(), c < '0' || c > '9')
 16         if(c == '-') op = 1;
 17     x = c - '0';
 18     while(c = getchar(), c >= '0' && c <= '9')
 19         x = x * 10 + c - '0';
 20     if(op) x = -x;
 21 }
 22 template <class T>
 23 void write(T x){    //又写读入优化又写输出优化的奆佬学姐 
 24     if(x < 0) putchar('-'), x = -x;
 25     if(x >= 10) write(x / 10);
 26     putchar('0' + x % 10);
 27 }
 28 
 29 const int N = 1e6 + 6, M = 3e5 + 6;
 30 int n, m;
 31 int prime[N], d[N], t[N];  
 32 bool p[N];  
 33 void init(int n){  
 34     d[1]=1; t[1]=0;  
 35     for (int i=2;i<=n;++i){  
 36         if(!p[i]) prime[++prime[0]]=i, d[i]=2, t[i]=1;  
 37         for (int j=1;j<=prime[0] && i*prime[j] <= n;++j){  
 38             p[i*prime[j]]=1;  
 39             if (!(i%prime[j])){
 40                 d[i*prime[j]]=d[i]/(t[i]+1)*(t[i]+2);
 41                 t[i*prime[j]]=t[i]+1;
 42                 break;
 43             }  
 44             else{
 45                 d[i*prime[j]]=d[i]*2;
 46                 t[i*prime[j]]=1;
 47             }  
 48         }   
 49     }
 50 }
 51 ll data[4 * M];
 52 int mx[4 * M], a[M];
 53 bool done[4 * M];
 54 
 55 void build(int k, int l, int r){    //种树 
 56     if(l == r){
 57         data[k] = mx[k] = a[l];
 58         if(mx[k] <= 2) done[k] = 1;
 59         return;
 60     }
 61     int mid = (l + r) >> 1;
 62     build(k << 1, l, mid);
 63     build(k << 1 | 1, mid + 1, r);
 64     data[k] = data[k << 1] + data[k << 1 | 1];
 65     mx[k] = max(mx[k << 1], mx[k << 1 | 1]);
 66     if(mx[k] <= 2) done[k] = 1;
 67 }
 68 void change(int k, int l, int r, int ql, int qr){    //这就是那个求约数个数的骚操作 
 69     if(l == r){
 70         data[k] = mx[k] = d[data[k]];
 71         if(mx[k] <= 2) done[k] = 1;
 72         return;
 73     }
 74     int mid = (l + r) >> 1;
 75     if(ql <= mid && !done[k << 1]) change(k << 1, l, mid, ql, qr);
 76     if(qr > mid && !done[k << 1 | 1]) change(k << 1 | 1, mid + 1, r, ql, qr);
 77     data[k] = data[k << 1] + data[k << 1 | 1];
 78     mx[k] = max(mx[k << 1], mx[k << 1 | 1]);
 79     if(mx[k] <= 2) done[k] = 1;
 80 }
 81 ll query(int k, int l, int r, int ql, int qr){    //这是求和 
 82     if(ql <= l && qr >= r) return data[k];
 83     int mid = (l + r) >> 1;
 84     ll ret = 0;
 85     if(ql <= mid) ret += query(k << 1, l, mid, ql, qr);
 86     if(qr > mid) ret += query(k << 1 | 1, mid + 1, r, ql, qr);
 87     return ret;
 88 }
 89 
 90 int main(){
 91 freopen("math.in","r",stdin);freopen("math.out","w",stdout);
 92     init(1e6 + 3);
 93     read(n), read(m);
 94     for(int i = 1; i <= n; i++) read(a[i]);
 95     build(1, 1, n);
 96     int op, l, r;
 97     while(m--){
 98         read(op), read(l), read(r);
 99         if(op == 1) change(1, 1, n, l, r);
100         else write(query(1, 1, n, l, r)), enter;
101     }
102         
103     return 0;
104 }

这题我懒得改

而且也不会改

所以只xjb写了几句注释

我也不是像ypq那样脑洞巨大的人是吧（