#include<bits/stdc++.h>
#define tnw 100000
#define intt long long
#define bgn mp[xx].begin()
#define ed mp[xx].end()
#define il inline
#define rg register
using namespace std;

vector<int>mp[5*tnw+5];
int n,m,a[tnw+5];
intt bt[tnw+5];

il int read(){
	int x=0;
    char ch=getchar();
    while(!isdigit(ch))
    	ch=getchar();
    while(isdigit(ch)){
    	x=(x<<3)+(x<<1)+(ch^48),
    	ch=getchar();
    }
    return x;
}

il void write(intt xx){
	if(xx>9)write(xx/10);
	putchar(xx%10+'0');
}

il void pout(int id,int xx){
	for(rg int j=1;j*j<=xx;j++){
		if(xx%j)continue;
		mp[j].push_back(id);
		if(xx/j^j)mp[xx/j].push_back(id);
	}
}

il void add(int id,intt xx){
	for(rg int i=id;i<=n;i+=i&-i){
		bt[i]+=xx;
	}
}

il intt sum(int id){
	intt ans=0;
	for(rg int i=id;i>0;i-=i&-i){
		ans+=bt[i];
	}
	return ans;
}

il void rag(int l,int r,int xx){
	vector<int>::iterator frm,tto,gn;
	frm=lower_bound(bgn,ed,l)-1;
	tto=lower_bound(bgn,ed,r+1)-1;
	if(frm+1==ed)return;
	for(gn=tto;gn!=frm;gn--){
		int now=*gn;
		if(a[now]%xx){
			mp[xx].erase(gn);
			continue;
		}
		a[now]/=xx;
		add(now,-a[now]*(xx-1));
		if(a[now]%xx){
			mp[xx].erase(gn);
		}
	}
}

signed main(){
	n=read();m=read();
	for(rg int i=1;i<=n;i++){
		a[i]=read();
		add(i,a[i]);
		pout(i,a[i]);
	}
	while(m--){
		int op,l,r,xx;
		op=read();l=read();r=read();
		if(op==1){
			xx=read();
			if(xx==1||mp[xx].empty())continue;
			rag(l,r,xx);
		}
		else{
			write(sum(r)-sum(l-1));
			putchar('\n');
		}
	}
	return 0;
}

帮忙优化，谢谢。

不理解为什么有一个博主线段树跑得飞快我树状数组直接T飞200ms+