// I also thought that there was a small chance that she likes me back. #include <bits/stdc++.h> using namespace std; // Do you think you'll ever remember me someday, or will I just fade away from your memory? #define LIFESUCK ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define str string #define mll map<ll, ll> #define vll vector<ll> #define pll pair<ll, ll> #define fi first #define se second #define all(c) c.begin(), c.end() #define pb push_back #define sz(s) s.size() #define debug cout << "I Love You\n"; #define fu(i, a, b) for (ll i = a; i <= b; i++) #define fd(i, b, a) for (ll i = b; i >= a; i--) #define Bitc(msk, j) ((msk >> j) & 1) #define _log(x) 63 - __builtin_clzll(x) #define LoveTime chrono::steady_clock::now().time_since_epoch().count() const ll Mod = 998244353; const ll inf = (1ll << 30); const ll lnf = (1ll << 60); // When time passes and things change... will you still remember someone like me? int64_t add(ll& a, ll b) { a += b; if (a >= Mod) a %= Mod; while (a < 0) a += Mod; return a; } int64_t mul(ll a, ll b) { a = 1ll * a * b % Mod; return a; } template <class X, class Y> bool minimize(X& x, Y y) { X eps = 1e-9; if (x > y + eps) { x = y; return 1; } return 0; } template <class X, class Y> bool maximize(X& x, Y y) { X eps = 1e-9; if (x + eps < y) { x = y; return 1; } return 0; } // I wonder… will I just become a distant memory to you one day? #define mxn 200'007 ll n, q, g[mxn]; vll graph[mxn]; struct Node { ll ans, gcd; vector<pll> pref, suf; Node() { ans = 0; gcd = 0; pref.clear(); suf.clear(); } void compress(vector<pll>& c) { mll mp; vector<pll> res; for(auto&[i, j]: c) mp[i] += j; for(auto&[i, j]: mp) res.pb({i, j}); swap(c, res); } Node friend operator+(const Node&Lft, const Node&Rgh) { Node res; res.gcd = __gcd(Lft.gcd, Rgh.gcd); res.pref = Lft.pref; res.suf = Rgh.suf; for(auto&[x, cnt]: Rgh.pref) res.pref.pb({__gcd(Lft.gcd, x), cnt}); for(auto&[x, cnt]: Lft.suf) res.suf.pb({__gcd(Rgh.gcd, x), cnt}); res.ans = Lft.ans + Rgh.ans; for(auto&[a, cnt1]: Lft.suf) for(auto&[b, cnt2]: Rgh.pref) if(__gcd(a, b) == 1) res.ans += (cnt1 * cnt2); res.compress(res.pref); res.compress(res.suf); return res; } }; struct SegmentTree { vector<Node> f; SegmentTree(ll _n = 0): f(4 * _n + 7, Node()) {} void update(ll id, ll l, ll r, ll pos, ll val) { if(r < pos || pos < l) return; if(l == r) { f[id].pref.clear(); f[id].suf.clear(); f[id].ans = (val == 1); f[id].gcd = val; f[id].pref.pb({val, 1}); f[id].suf.pb({val, 1}); return; } ll mid = l + (r - l) / 2; update(id << 1, l, mid, pos, val); update(id << 1 | 1, mid + 1, r, pos, val); f[id] = f[id << 1] + f[id << 1 | 1]; } Node get(ll id, ll l, ll r, ll u, ll v) { if(r < u || v < l) return Node(); if(u <= l && r <= v) return f[id]; ll mid = l + (r - l) / 2; Node Lft = get(id << 1, l, mid, u, v); Node Rgh = get(id << 1 | 1, mid + 1, r, u, v); return Lft + Rgh; } }; // The world is still beautiful, only it’s a pity that you are no longer among the living. void lovesper(const ll& TestCase) { cin >> n >> q; SegmentTree st(n); fu(i, 1, n) { ll x; cin >> x; st.update(1, 1, n, i, x); } fu(qst, 1, q) { ll o; cin >> o; if(o == 1) { ll pos, x; cin >> pos >> x; st.update(1, 1, n, pos, x); } else { ll l, r; cin >> l >> r; ll mie = (r - l + 1); cout << mie * (mie + 1) / 2 - st.get(1, 1, n, l, r).ans << '\n'; } } } // In the future, each of us will have our own path.. // ...But no matter where we go, we will always be a beautiful part of each other’s memories. signed main() { LIFESUCK #define name "lovesper" // freopen(name".inp", "r", stdin); // freopen(name".out", "w", stdout); ll Test = 1; // cin >> Test; fu(i, 1, Test) { lovesper(i); if (i < Test) cout << '\n'; } return 0; }