RT，慕名而来，写了写，在弱化版调了调，用了很多 vector，还用了 sort，结果直接过了？

Code:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define getchar() (xS == xTT && (xTT = (xS = xB) + fread(xB , 1 , 1 << 23 , stdin) ,xS == xTT) ? 0 : *xS++)
#define putchar(x) (p3 - obuf < 1000000) ? (*p3++ = x) : (fwrite(obuf , p3 - obuf , 1 , stdout) , p3 = obuf , *p3++ = x)
char xch,xB[1<<23],*xS=xB,*xTT=xB,obuf[1000000],*p3=obuf;
inline int read(){
    char op = getchar();
    int x = 0, f = 1;
    while(op < '0' || op > '9'){
        f = (op == '-' ? -1 : 1);
        op = getchar();
    }
    while (op >= '0' && op <= '9') {
        x = (x << 1) + (x << 3) + (op ^ 48);
        op = getchar();
    }
    return x * f;
}
static char cc[20];
template <class T>
inline void pt(T x){
    int len = 0;
    if(!x) return putchar('0') , void();
    if(x < 0){
        x = -x;
		putchar('-');
	}
    while(x){
        cc[len++] = x % 10 + '0';
		x /= 10;
	}
    while(len--) putchar(cc[len]);
}
vector <int> fa[500005] , id[500005] , qwq[500005];
int n , q , a[1000005];
bool vis[500005];
inline int Find(int x , int y){
    if(y>=(int)fa[x].size())return y;
    return fa[x][y]==y?y:fa[x][y]=Find(x,fa[x][y]);
}
inline void xxs(){
    for(int i = 2;i <= 500000;i++){
        for(int j=i;j<=500000;j+=i){
            for(auto v:qwq[j]){
                fa[i].push_back(fa[i].size());
                id[i].push_back(v);
            }
        }
    }
}
namespace BIT{
    ll c[500005];
    inline void add(int x,int y){
        for(;x<=n;x+=x&(-x))c[x]+=y;
    }
    inline ll query(int x){
        ll ans=0;
        for(;x;x-=x&(-x))ans+=c[x];
        return ans;
    }
};
using namespace BIT;
int lst;
signed main(){
    n=read(),q=read();
    for(int i=1;i<=n;i++)a[i]=read(),qwq[a[i]].push_back(i),add(i,a[i]);
    xxs();
    while(q--){
        // cerr<<"OK\n";
        int opt=read(),l=read(),r=read(),x;
        if(opt==1){
            x=read();
            if(x==1)continue;
            if(!vis[x]){
                sort(id[x].begin(),id[x].end());
                vis[x]=1;
            }
            l=lower_bound(id[x].begin(),id[x].end(),l)-id[x].begin();
            // cerr<<l<<' '<<fa[x][l]<<"dw\n";
            for(l=Find(x,l);l<(int)id[x].size();l=Find(x,l+1)){
                int i=id[x][l];
                if(i>r)break;
                if(a[i]%x==0){
                    add(i,-1*a[i]);
                    a[i]/=x;
                    add(i,a[i]);
                }
                if(a[i]%x)fa[x][l]=l+1;
                // cerr<<l<<' '<<id[x].size()<<' '<<i<<' '<<a[i]<<' '<<Find(x,l+1)<<endl;
            }
            // cerr<<"end\n";
        }
        else{
            lst=query(r)-query(l-1);
            pt(lst),putchar('\n');
            // cerr<<lst<<endl;
        }
        // cerr<<"end\n";
    }
	fwrite(obuf , p3 - obuf , 1 , stdout);
    return 0;
}