rt.

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

static inline int lcm(int x,int y) {
    if(x==0||y==0) return -1;
    return x/__gcd(x,y)*y;
}

int n,m;
int a[100005];
int d[400005];
int f[400005];
static inline void build(int s,int t,int p) {
    if(s==t) {
        d[p]=a[s];
        f[p]=d[p];
        return ;
    }
    int mid=(s+t)>>1;
    build(s,mid,p<<1);
    build(mid+1,t,p<<1|1);
    d[p]=d[p<<1]+d[p<<1|1];
    f[p]=lcm(f[p<<1],f[p<<1|1]);    // 处理最小公倍数
    f[p]=max(f[p],1ll);
}
static inline void update(int l,int r,int s,int t,int c,int p) {
    if(l>t||r<s) return ;
    if(l<=s&&r>=t&&(f[p]<=1||f[p]%c!=0)) return ;   // 注释掉这一行可以保证正确 但是 TLE
                                                    // 加上这一行会 WA
                                                    // 剪去一些无效操作 (进入没有 x 的倍数的子树或进入全是 0/1 的子树)
    if(s==t) {
        if(l<=s&&r>=t&&d[p]%c==0) {
            d[p]/=c;
        }
        f[p]=d[p];
        return ;
    }
    int mid=(s+t)>>1;
    if(l<=mid) update(l,r,s,mid,c,p<<1);
    if(r>mid) update(l,r,mid+1,t,c,p<<1|1);
    d[p]=d[p<<1]+d[p<<1|1];
    f[p]=lcm(f[p<<1],f[p<<1|1]);
    f[p]=max(f[p],1ll);
}
static inline int query(int l,int r,int s,int t,int p) {
    if(l>t||r<s) return 0;
    if(l<=s&&r>=t) return d[p];
    int mid=(s+t)>>1;
    int ret=0;
    if(l<=mid) ret+=query(l,r,s,mid,p<<1);
    if(r>mid) ret+=query(l,r,mid+1,t,p<<1|1);
    return ret;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i) {
        cin>>a[i];
    }
    build(1,n,1);
    while(m--) {
        int op;
        cin>>op;
        if(op==1) {
            int l,r,x;
            cin>>l>>r>>x;
            if(x==1) continue;  // 无效操作
            update(l,r,1,n,x,1);
        }
        else if(op==2) {
            int l,r;
            cin>>l>>r;
            cout<<query(l,r,1,n,1)<<endl;
        }
    }
    return 0;
}

思路：基于最小公倍数判断区间是否有符合要求的倍数，经过此优化不会 TLE。（但是会 WA）

提交记录

恳请各位大佬调代码（给份 hack 数据也十分感谢）