打了个暴力的动态开点线段树，时空复杂度$O(n\sqrt n \log^2 n)$的，结果过了？？？

不是讨论区题解（开O2卡着过的

#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
	T t=0;
	char k;
	bool vis=0;
	do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define ll long long
int a[100005],s;
ll b[200005];
struct node{
	node *l,*r;
	int v;
	node(){l=r=NULL;v=0;}
}*root[500005];
void upd(int x,int v){
	int c=a[x]-a[x]/v;a[x]-=c;
	for(int i=x;i<=s;i+=i&-i)b[i]-=c;
}ll query(int x){
	ll t=0;
	while(x)t+=b[x],x&=x-1;
	return t;
}
void insert(node *&x,int v,int l,int r){
	if(!x)x=new node();
	x->v|=v;
	if(l==r)return;
	int mid=l+r>>1;
	if(v<=mid)insert(x->l,v,l,mid);
	else insert(x->r,v,mid+1,r);
}
void div(node *x,int v,int l,int r,int tl,int tr){
	if(!x||!x->v||r<tl||tr<l)return;
	if(tl==tr){
		if(a[tl]%v){x->v=0;return;}
		upd(tl,v);
		if(a[tl]%v)x->v=0;
	}else{
		int mid=tl+tr>>1;
		div(x->l,v,l,r,tl,mid);
		div(x->r,v,l,r,mid+1,tr);
		x->v=(x->l?x->l->v:0)|(x->r?x->r->v:0);
	}
}
int main(){
	s=read;int m=read;
	for(int i=1;i<=s;++i)b[i+(i&-i)]+=b[i]+=a[i]=read;
	for(int i=1;i<=s;++i)
		for(int j=1;j*j<=a[i];++j)
			if(!(a[i]%j)){
				insert(root[j],i,1,s);
				if(j*j!=a[i])insert(root[a[i]/j],i,1,s);
			}
	while(m--)
		if(read&1){
			int l=read,r=read,x=read;
			if(x==1)continue;
			div(root[x],x,l,r,1,s);
		}else{
			int l=read,r=read;
			printf("%lld\n",query(r)-query(l-1));
		}
	return 0;
}