RT 线段树求调 T在#2，3000ms

#include <bits/stdc++.h>
using namespace std;
const int ve = 5e6 + 7;
const int _ = 1e5 + 7;
vector <int> E[ve];
int phi[ve], dep[ve], prime[ve], vis[ve], Pcnt;
int dfn[ve], rev[ve], a[_], Icnt;
struct SegTree {
    int maxn, minn, val;
    int sum, lazy;
} T[_ << 2];
void Euler(int V) {
    phi[1] = 1;
    for (int i = 2; i <= V; ++i) {
        if (!vis[i]) {prime[++Pcnt] = i; phi[i] = i - 1;}
        for (int j = 1, v = prime[j]; j <= Pcnt and v * i <= V; ++j) {
            vis[v * i] = 1;
            if (i % v == 0) {phi[i * v] = phi[i] * v; break;}
            else phi[i * v] = phi[i] * phi[v];
        }
    }
}
void Dfs(int u) {
    dfn[u] = ++Icnt; rev[Icnt] = u;
    for (int v : E[u]) 
        {dep[v] = dep[u] + 1; Dfs(v);}
}
int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    while (dep[u] > dep[v]) u = phi[u];
    while (u != v) {u = phi[u]; v = phi[v];}
    return u;
}
int ls(int p) {return p << 1;}
int rs(int p) {return p << 1 | 1;}
void Push_up(int p) {
    T[p].lazy = T[ls(p)].lazy & T[rs(p)].lazy;
    T[p].sum = T[ls(p)].sum + T[rs(p)].sum;
    T[p].maxn = max(T[ls(p)].maxn, T[rs(p)].maxn);
    T[p].minn = min(T[ls(p)].minn, T[rs(p)].minn);
}
SegTree Merge(SegTree T1, SegTree T2) {
    SegTree res;
    res.lazy = res.val = 0;
    res.maxn = max(T1.maxn, T2.maxn);
    res.minn = min(T1.minn, T2.minn);
    res.sum = T1.sum + T2.sum;
    return res;
}
void Build(int p, int l, int r) {
    if (l == r) {
        T[p].val = a[l];
        T[p].lazy = (a[l] == 1);
        T[p].sum = dep[a[l]];
        T[p].maxn = T[p].minn = dfn[a[l]];
        return ;
    }
    int mid = l + r >> 1;
    Build(ls(p), l, mid); Build(rs(p), mid + 1, r);
    Push_up(p);
}
void Change(int p, int l, int r, int L, int R) {
    if (l > R or r < L or T[p].lazy) return ;
    if (l == r) {
        T[p].val = phi[T[p].val];
        T[p].lazy = (T[p].val == 1);
        T[p].sum--; 
        T[p].maxn = T[p].minn = dfn[T[p].val];
        return ;
    }
    int mid = l + r >> 1;   
    if (L <= mid) Change(ls(p), l, mid, L, R);
    if (R > mid) Change(rs(p), mid + 1, r, L, R);
    Push_up(p);
}
SegTree Query(int p, int l, int r, int L, int R) {
    if (l > R or r < L) return {-1, ve, 0, 0, 0}; 
    if (L <= l and r <= R) return T[p];
    int mid = l + r >> 1;
    SegTree res = {-1, ve, 0, 0, 0};
    if (L <= mid) res = Query(ls(p), l, mid, L, R);
    if (R > mid) res = Merge(res, Query(rs(p), mid + 1, r, L, R));
    return res;
}
signed main() {
    int n, m, V = 0; cin >> n >> m;
    for (int i = 1; i <= n; ++i) 
        {cin >> a[i]; V = max(V, a[i]);}
    Euler(V); 
    for (int i = 2; i <= V; ++i)
        E[phi[i]].push_back(i);
    dep[1] = 1; Dfs(1); 
    Build(1, 1, n); 
    for (int i = 1; i <= m; ++i) {
        int op, l, r; cin >> op >> l >> r;
        if (op == 1){ Change(1, 1, n, l, r); }
        else {
            SegTree res = Query(1, 1, n, l, r); 
            int lca = LCA(rev[res.maxn], rev[res.minn]);
            cout << res.sum - (r - l + 1) * dep[lca] << endl;
        }
    }
    return 0;
}