lxl题，现在稳定在502ms~504ms，就差一点点卡不过去。

#include<bits/stdc++.h>
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
typedef long long ll;
const int N=100009;
const int A=500009; 
inline int read_int(){
	int s=0; char ch=getchar();
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57){s=(s<<1)+(s<<3)+ch-48; ch=getchar();}
	return s;
}
inline ll read_ll(){
	ll s=0; char ch=getchar();
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57){s=(s<<1)+(s<<3)+ch-48; ch=getchar();}
	return s;
}
inline void write(ll x){if(x>9)write(x/10); putchar(x%10+48);}
inline void updmx(int&x,int m){if(x<m)x=m;}
int n,q,mx,x[N],cnt[A],*p[A],_o[N*405],*top=_o;
ll bit[N],lastans;
#define LSB(x) ((x)&-(x))
inline void add(int i,int x){while(i<=n)bit[i]+=x,i+=LSB(i);}
inline ll query(int i){ll ret=0; while(i)ret+=bit[i],i-=LSB(i); return ret;}
struct UFS{
	int *fa;
	inline void init(int m){for(int i=0;i<m;i++)fa[i]=i;}
	inline int root(int x){return fa[x]==x?x:fa[x]=root(fa[x]);}
} T[A];
inline void div(int l,int r,int d){
	if(d==1)return;
	l=lower_bound(p[d],p[d]+cnt[d],l)-p[d];
	r=upper_bound(p[d],p[d]+cnt[d],r)-p[d]-1;
	if(l>r)return;
	for(int u=T[d].root(l);u<=r;){
		int pos=p[d][u];
		if(x[pos]%d==0)add(pos,x[pos]/d-x[pos]),x[pos]/=d;
		if(u>=r)break;
		if(x[pos]%d)u=T[d].fa[u]=T[d].root(u+1);
		else u=T[d].root(u+1);
	}
}
int main(){
	n=read_int(); q=read_int();
	for(int i=1;i<=n;i++)add(i,x[i]=read_int()),updmx(mx,x[i]),cnt[x[i]]++;
	for(int i=1;i<=mx;i++)for(int j=i<<1;j<=mx;j+=i)cnt[i]+=cnt[j];
	for(int i=1;i<=mx+1;i++)if(cnt[i]){
		p[i]=top; top+=cnt[i];
		T[i].fa=top; T[i].init(cnt[i]); top+=cnt[i];
		cnt[i]=0;
	}
	for(int i=1;i<=n;i++)
		for(int d=1;d*d<=x[i];d++)
			if(x[i]%d==0){
				p[d][cnt[d]++]=i;
				if(d*d!=x[i])p[x[i]/d][cnt[x[i]/d]++]=i;
			}
	while(q--){
		int op=read_int(); ll l=read_ll()^lastans,r=read_ll()^lastans;
		if(op==1)div(l,r,read_ll()^lastans);
		else{write(lastans=(query(r)-query(l-1))); putchar('\n');}
	}
	return 0;
}

为了卡常，码风非常难看，望谅解。

你咕评测机太慢了