题目链接

题意：给出一个序列 \(a(n)\)，需要支持以下两个操作
1 l r x 将 \([l,r]\) 中 \(x\) 的倍数除以 \(x\)
2 l r 求 \([l,r]\) 的和。
\(1 \leq n \leq 10^5\)，\(1 \leq a_i \leq 5 \times 10^5\)

真·卡常毒瘤题，加强版还没过
不难发现每个数最多除 \(\log(500000)\) 次，所以总次数不会超过 \(2 \times 10^6\)，至于求和，可以用树状数组维护。
所以这道题的难点就变为了怎么找出 \(x\) 的倍数。
我们对于每个 \(x\) 建一棵平衡树，里面插入所有 \(a_i\) 是 \(x\) 的倍数的 \(i\)。
对于一次 \(1\) 操作，只需将第 \(x\) 棵树的 \([l,r]\) 截出来，将数中的 \(x\) 的倍数都除以 \(x\)，如果除完之后不是 \(x\) 的倍数，就将它从这个平衡树删除。
就 好 了
代码：（大概要开 O2 才能过）

#include <bits/stdc++.h>
using namespace std;
#define fz(i,a,b)	for(register int i=a;i<=b;i++)
#define fd(i,a,b)	for(register int i=a;i>=b;i--)
//#define int long long
typedef long long ll;
inline int read(){
	int x=0,neg=1;char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	neg=-1;
		c=getchar();
	}
	while(isdigit(c))	x=x*10+c-'0',c=getchar();
	return x*neg;
}
inline void print(ll x){
	(x<=9)?(putchar(x+'0')):(print(x/10),putchar(x%10+'0'));
}
int n=read(),m=read(),a[100005];
int dels[500005],dels_cnt;
ll bit[100005];
inline void add(int x,int y){
	for(int i=x;i<=n;i+=(i&(-i)))	bit[i]+=y;
}
inline ll query(int x){
	ll sum=0;
	for(int i=x;i;i-=(i&(-i)))	sum+=bit[i];
	return sum;
}
struct node{
	int ch[2],ind,key;
};
int qt[100005],qts=0;
node s[20000005];
int rt[500005];
int cnt=0;
vector<int> f[500005];
inline int newnode(int ind){
	s[++cnt].ind=ind;
	s[cnt].key=rand();
	return cnt;
}
inline void build(int &k,int l,int r){
	int mid=(l+r)>>1;
	k=newnode(qt[mid]);
	if(l^mid)	build(s[k].ch[0],l,mid-1);
	if(mid^r)	build(s[k].ch[1],mid+1,r);
}
inline void split(int k,int val,int &a,int &b){
	if(!k){a=b=0;return;}
	(val<s[k].ind)?(b=k,split(s[k].ch[0],val,a,s[k].ch[0])):(a=k,split(s[k].ch[1],val,s[k].ch[1],b));
}
inline int merge(int a,int b){
	if(!a||!b)	return a+b;
	return (s[a].key>s[b].key)?(s[a].ch[1]=merge(s[a].ch[1],b),a):(s[b].ch[0]=merge(a,s[b].ch[0]),b);
}
inline void del(int ind,int x){
	int k1,k2,k3;
	split(rt[x],ind-1,k1,k2);
	split(k2,ind,k2,k3);
	rt[x]=merge(k1,k3);
}
inline void dfs(int k,int x){
	if(!k)	return;
	dfs(s[k].ch[0],x);
	if(a[s[k].ind]%x==0)	add(s[k].ind,-a[s[k].ind]),a[s[k].ind]/=x,add(s[k].ind,a[s[k].ind]);
	if(a[s[k].ind]%x!=0)	dels[++dels_cnt]=s[k].ind;
	dfs(s[k].ch[1],x);
}
inline void solve(int x,int l,int r){
	if(x==1)	return;
	int k1,k2,k3;
	split(rt[x],l-1,k1,k2);
	split(k2,r,k2,k3);
	dels_cnt=0;
	dfs(k2,x);
	rt[x]=merge(merge(k1,k2),k3);
	fz(i,1,dels_cnt)	del(dels[i],x);
}
signed main(){
	srand(time(0));
	fz(i,1,n)	a[i]=read(),add(i,a[i]);
	fz(i,1,n){
		if(!a[i])	continue;
		for(int j=1;j*j<=a[i];j++){
			if(a[i]%j==0){
				f[j].push_back(i);
				if(a[i]/j!=j)	f[a[i]/j].push_back(i);
			}
		}
	}
	fz(i,1,500000){
		if(f[i].size()){
			qts=0;
			for(int j=0;j<f[i].size();j++){
				qt[++qts]=f[i][j];
			}
			build(rt[i],1,qts);
		}
	}
	ll ans=0;
	while(m--){
		int opt=read();
		if(opt&1){
			int l=read(),r=read(),x=read();
			//l^=ans;r^=ans;x^=ans;
			solve(x,l,r);
		}
		else{
			int l=read(),r=read();
			//l^=ans;r^=ans;
			ans=query(r)-query(l-1);
			print(ans);putchar('\n');
		}
	}
}