1797E - Li Hua and Array - CodeForces Solution

/**
 *  Author: Anil Byar
**/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;
using namespace std;

// template<class T>
// using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;



#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()
#define uniq(v) v.erase(unique(all(v)), v.end())
#define ft first
#define sd second
#define pb push_back
#define eb emplace_back

// Source: https://codeforces.com/blog/entry/68809
// { start
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
// } end


typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vl> vvl;

#define dbg if(0)

const ll MOD = 1e9+7;
const ll MOD9 = 998244353;
const ll INFLL = 1e18+5;
const int INF = 1e9;

void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;}
ll power(ll x, ll y, ll mod){if (y==0) return 1;ll ret = power(x, y/2, mod);ret *= ret;ret%=mod;if (y&1) ret *= x;return ret%mod;}
ll modinv(ll x, ll mod = MOD) {return power(x, mod-2, mod);}

template<class T> bool chmin(T& a, T b){return (a>b?a=b,1:0);}
template<class T> bool chmax(T& a, T b){return (a<b?a=b,1:0);}
template<class T>
istream& operator>>(istream&in, vector<T>&v){
    for (T& x:v) in>>x;
    return in;
}
template<class T>
ostream& operator<<(ostream&out, vector<T>&v){
    for (T& x:v) out<<x<<' ';
    cout<<'\n';
    return out;
}
// use ?: with brackets (?:)
// check for overflow
// think about dp
// Read the statement carefully



const int N = 5e6+1;
const int M = 5;
int p[N][M];
vi adj[N];
int phi[N];
int dep[N];

void calcPhi(){
    int lp[N];
    iota(lp, lp+N, 0);
    for (int i = 2;i*i<N;i++){
        if (lp[i]==i){
            for (int j = i;j<N;j+=i){
                lp[j] = i;
            }
        }
    }
    phi[1] = 1;
    for (int i = 2;i<N;i++){
        if ((i/lp[i])%lp[i]==0) phi[i] = phi[i/lp[i]] * lp[i];
        else phi[i] = phi[i/lp[i]] * (lp[i]-1);
        adj[phi[i]].pb(i);
    }
}

void dfs(int node){
    for (int x:adj[node]){
        dep[x] = dep[node] + 1;
        p[x][0] = node;
        // cout<<node<<" "<<x<<endl;
        dfs(x);
    }
}

int kup(int a, int h){
    for (int i = 0;i<M;i++){
        if (h>>i&1) a = p[a][i];
    }
    return a;
}
int LCA(int a, int b){
    if (a==1 || b==1) return 1;
    if (dep[a]>dep[b]) swap(a, b);
    b = kup(b, dep[b]-dep[a]);
    if (a==b) return a;
    for (int k = M-1;k>=0;k--) {
        if (p[a][k]!=p[b][k]) a = p[a][k], b = p[b][k];
    }
    return p[a][0];
}

struct Node{
    int cost = 0, cont = 0, mx = 1, lca = 1;
    friend Node operator+(const Node& a, const Node& b){
        if (b.cont==0) return a;
        else if (a.cont==0) return b;
        Node tmp;
        tmp.lca = LCA(a.lca, b.lca);
        tmp.cont = a.cont+b.cont;
        tmp.cost = a.cost+b.cost+(dep[a.lca] - dep[tmp.lca])*a.cont + (dep[b.lca] - dep[tmp.lca]) * b.cont;
        tmp.mx = max(a.mx, b.mx);
        return tmp;
    }
};


// Source: https://codeforces.com/blog/entry/18051
template <class T> struct SegTree{
    int n; T ID;
    std::vector<T> tree;
    T oper(T a, T b){return a+b;} // update this operation function according to need
    SegTree(int _n, T id){
        n = 1;ID = id;
        while(n<_n) n<<=1;
        tree.resize(2*n, ID);
    }
    void build(std::vector<T> list){
        for (int i = 0;i<(int) list.size();++i) tree[i+n] = list[i];
        for (int i = n-1;i>0;--i) tree[i] = oper(tree[i<<1], tree[i<<1|1]);
    }

    void upd(int l, int r, int x, int lx, int rx){
        if (l>=rx || r<=lx || tree[x].mx==1) return;
        if (rx-lx==1){
            if (tree[x].lca!=1){
                tree[x].lca = p[tree[x].lca][0];
                // tree[x].cost = 0;
                // tree[x].cont = 1;
                tree[x].mx = tree[x].lca;
            }
            return;
        }
        int mid = (lx+rx)/2;
        upd(l, r, 2*x, lx, mid);
        upd(l, r, 2*x+1, mid, rx);
        tree[x] = tree[2*x]+tree[2*x+1];
    }

    void upd(int l, int r){
        upd(l, r, 1, 0, n);
    }

    T query(int l, int r){// indexing is from 0 to n-1, gives answer to [l, r)
        T left = ID, right = ID; // left and right for non associative operation
        for (l+=n, r+=n;l<r;l>>=1, r>>=1){
            if (l&1) left = oper(left, tree[l++]);
            if (r&1) right = oper(tree[--r], right);
        }
        return oper(left, right);
    }
};


void solve(){
    calcPhi();
    // for (int i = 1;i<N;i++) cout<<i<<" "<<phi[i]<<endl;
    dfs(1);
    for (int i = 1;i<M;i++){
        for (int j = 1;j<N;j++){
            p[j][i] = p[p[j][i-1]][i-1];
        }
    }
    int n, m;cin>>n>>m;
    vector<Node> a(n);
    for (int i = 0;i<n;i++){
        cin>>a[i].mx;
        a[i].lca = a[i].mx;
        a[i].cont = 1;
        a[i].cost = 0;
    }
    SegTree<Node> seg(n, Node());
    seg.build(a);
    // ll sum = 0, mx = 0;
    // for (int i = 1;i<N;i++) sum += dep[i], mx = max(mx, dep[i]);
    // cout<<sum<<" "<<sum/N<<" "<<mx;
    for (int i = 0;i<m;i++){
        int t, l, r;cin>>t>>l>>r;l--;
        if (t==1){
            seg.upd(l, r);
        } else {
            cout<<seg.query(l, r).cost<<'\n';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);


#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    freopen("debug.dbg", "w", stderr);
    int tt = clock();
#endif

    int t=1, i = 1;
    // cin>>t;
    while(t--){
        // cout<<"Case #"<<i++<<": ";
        solve();
        // cout<<'\n';
    }
#ifndef ONLINE_JUDGE
    cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl;
    tt = clock();
#endif
}