题解 | 二小姐的区间查询

线段树

考虑维护区间上各个数与495最大公约数的个数和区间上的答案，495的约数只有{1,3,5,9,11,15,33,45,55,99,165,495}

合并区间的个数的时候对应的加一下就行，合并答案的时候父节点的答案 = 左节点的答案 + 右节点的答案 + 跨左右产生的答案

/*

##     ##   #######   ########    ###     ########  ##   ##
##     ##  ##     ##     ##      ## ##    ##    ##  ##   ##
##     ##  ##     ##     ##     ##   ##   ##    ##  ##   ##
#########  ##     ##     ##    ##     ##  ########  ##   ##
##     ##  ##     ##     ##    #########  ##  ##    ##   ##
##     ##  ##     ##     ##    ##     ##  ##   ##   ##   ##
##     ##   #######      ##    ##     ##  ##    ##   #####

*/
//region define
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define endl '\n'
#define openfile freopen("D:\\users\\Desktop\\alorighmStudy\\in.txt", "r", stdin);
#define rep(i,a,b) for(int i = a ; i <= b ; i++)
#define per(i,a,b) for(int i = a ; i >= b ; i--)
using namespace std;
typedef long long ll;
//endregion
const int MAXN = 2e5 + 10;
int arr[MAXN];
vector<int> sp = {1,3,5,9,11,15,33,45,55,99,165,495};
map<int,int> mp;
vector<pair<int,int>> matchs;
int gcd(int a,int b) {
    return b == 0 ? a : gcd(b,a%b);
}
struct node{
    int v[12];
    ll ans;
    node() {
        memset(v, 0, sizeof(v));
        ans = 0;
    }
};
void init() {
    int cnt = 0;
    for (auto& v : sp) {
        mp[v] = cnt++;
    }
    rep(i,0,11) {
        rep(j,0,11) {
            if ((sp[i] * sp[j]) % 495 == 0)matchs.push_back({i,j});
        }
    }
}
node tree[MAXN << 2];
inline node hb(node x,node y) {
    node fa = node();
    rep(j,0,11) {
        fa.v[j] = x.v[j] + y.v[j];
    }
    fa.ans = x.ans + y.ans;
    for (auto& [i,j] : matchs) {
        fa.ans += x.v[i] * y.v[j];
    }
    return fa;
}
void up(int i) {
    tree[i] = hb(tree[i<<1],tree[i<<1|1]);
}
void build(int l,int r,int i) {
    if (l == r) {
        tree[i] = node();
        int val = gcd(495,arr[l]);
        tree[i].v[mp[val]]++;
    }
    else {
        int mid = (l + r) >> 1;
        build(l,mid,i<<1),build(mid + 1,r,i<<1|1);
        up(i);
    }
}
void update(int p,int v,int l,int r,int i) {
    if (p == l && p == r) {
        tree[i] = node();
        int val = gcd(v,495);
        tree[i].v[mp[val]]++;
    }
    else {
        int mid = (l + r) >> 1;
        if (p <= mid)update(p,v,l,mid,i<<1);
        else update(p,v,mid+1,r,i<<1|1);
        up(i);
    }
}
node query(int jobl,int jobr,int l,int r,int i) {
    if (jobl > r || jobr < l) return node();
    if (jobl <= l && jobr >= r) {
        return tree[i];
    }
    int mid = (l + r)>>1;
    if (jobr <= mid) return query(jobl, jobr, l, mid, i<<1);
    if (jobl > mid) return query(jobl, jobr, mid+1, r, i<<1|1);
    return hb(query(jobl,jobr,l,mid,i<<1),query(jobl,jobr,mid+1,r,i<<1|1));
}
void solve() {
    //交代码之前关openfile
    int n,q;
    cin >> n >> q;
    init();
    rep(i,1,n) {
        cin >> arr[i];
    }
    build(1,n,1);
    rep(i,1,q) {
        int opt;
        cin >> opt;
        if (opt == 1) {
            int x,y;
            cin >> x >> y;
            update(x,y,1,n,1);
        }
        else {
            int l,r;
            cin >> l >> r;
            node ans = query(l,r,1,n,1);
            cout << ans.ans << endl;
        }
    }
}
signed main() {
    // openfile
    IOS;
    int TTTT = 1;
    // cin >> TTTT;
    while (TTTT--) {
        int T = 1;
        // cin >> T;
        while (T--) {
            solve();
        }
    }
    return 0;
}