题目：CF1797E

代码：

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
#define MAXM 5000001

int n, m, opt, cnt, l, r;
int a[MAXN];
int phi[MAXM], dfn[MAXM], dfn2[MAXM];
int dep[MAXM], top[MAXM], siz[MAXM], son[MAXM], fa[MAXM];
list<int> pri;
list<int> e[MAXM];
bool np[MAXM];

void dfs1(int x){
    dep[x] = dep[fa[x]] + 1;
    siz[x] = 1;
    dfn[x] = ++cnt;
    dfn2[cnt] = x;
    for (auto i: e[x]){
        dfs1(i);
        siz[x] += siz[i];
        if (siz[son[x]] < siz[i]) son[x] = i;
    }
}

void dfs2(int x, int tp){
    top[x] = tp;
    if (son[x]) dfs2(son[x], tp);
    for (auto i: e[x]){
        if (i ^ son[x]) dfs2(i, i);
    }
}

int LCA(int x, int y){
    while (top[x] ^ top[y]){
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) return x;
    return y;
}

void init(int n){
    phi[1] = 1;
    for (int i(2); i<=n; ++i){
        if (!np[i]){
            phi[i] = i-1;
            pri.push_back(i);
        }

        for (auto j: pri){
            if (i*j > n) break;
            np[i*j] = 1;
            if (i % j == 0){
                phi[i*j] = phi[i] * j;
                break;
            }
            phi[i*j] = phi[i] * phi[j];
        }
    }

    for (int i(2); i<=n; ++i){
        e[phi[i]].push_back(i);
        fa[i] = phi[i];
    }
    dfs1(1);
    dfs2(1, 1);
}

struct Node{
    int l, r;
    int maxn, minn;
    long long sum;
};

struct Seg{
    Node tree[MAXN];
    void push_up(int p){
        tree[p].minn = min(tree[p<<1].minn, tree[p<<1|1].minn);
        tree[p].maxn = max(tree[p<<1].maxn, tree[p<<1|1].maxn);
        tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
    }

    void build(int l, int r, int p){
        tree[p].l = l;
        tree[p].r = r;
        if (l == r){
            tree[p].maxn = tree[p].minn = dfn[a[l]];
            tree[p].sum = dep[a[l]];
            return;
        }

        int mid((l+r)>>1);
        build(l, mid, p<<1);
        build(mid+1, r, p<<1|1);
        push_up(p);
    }

    void modify(int L, int R, int p){
        if (tree[p].l == tree[p].r){
            tree[p].maxn = tree[p].minn = dfn[a[tree[p].l] = fa[a[tree[p].l]]];
            --tree[p].sum;
            return;
        }

        int mid((tree[p].l+tree[p].r)>>1);
        if (L <= mid && tree[p<<1].maxn > 1) modify(L, R, p<<1);
        if (R > mid && tree[p<<1|1].maxn > 1) modify(L, R, p<<1|1);
        push_up(p);
    }

    int query1(int L, int R, int p){
        if (tree[p].l >= L && tree[p].r <= R) return tree[p].minn;
        int mid((tree[p].l+tree[p].r)>>1), res(INT_MAX);
        if (L <= mid) res = min(res, query1(L, R, p<<1));
        if (R > mid) res = min(res, query1(L, R, p<<1|1));
        return res;
    }

    int query2(int L, int R, int p){
        if (tree[p].l >= L && tree[p].r <= R) return tree[p].maxn;
        int mid((tree[p].l+tree[p].r)>>1), res(0);
        if (L <= mid) res = max(res, query2(L, R, p<<1));
        if (R > mid) res = max(res, query2(L, R, p<<1|1));
        return res;
    }

    int query3(int L, int R, int p){
        if (tree[p].l >= L && tree[p].r <= R) return tree[p].sum;
        int mid((tree[p].l+tree[p].r)>>1), res(0);
        if (L <= mid) res += query3(L, R, p<<1);
        if (R > mid) res += query3(L, R, p<<1|1);
        return res;
    }
}tr;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init(MAXM-1);

    cin >> n >> m;
    for (int i(1); i<=n; ++i) cin >> a[i];
    tr.build(1, n, 1);

    while (m--){
        cin >> opt >> l >> r;
        if (opt == 1) tr.modify(l, r, 1);
        else{
            int lca(LCA(dfn2[tr.query1(l, r, 1)], dfn2[tr.query2(l, r, 1)]));
            cout << tr.query3(l, r, 1)-(r-l+1)*dep[lca] << '\n';
        }
    }

    return 0;
}

在 Luogu IDE 中运行样例一直提示内存超限。

但是感觉题解和我的都差不多呀，他们就可以。

哪里出问题了？