rt，FHQ 62pts，TLE #1,#5,#34,#35

求助，谢谢

#include<stdio.h>
#include<stdlib.h>
#include<vector>
typedef long long ll;
const int maxn = 5e5 + 1;
const int max_size = 2e7 + 1;
#ifdef ONLINE_JUDGE
static char buf[1000000],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#endif
inline int Read(){
	register int x = 0;
	register char c = getchar();
	for(;c < '0' || c > '9';c = getchar());
	for(;c >= '0' && c <= '9';c = getchar()) x = x * 10 + (c ^ '0');
	return x; 
}
int n,m;
std::vector<int> value[maxn];
int a[maxn],tmp[maxn],len = 0;
int lc[max_size],rc[max_size],id[max_size],heap[max_size],siz[max_size],cnt = 0,rt[maxn];
inline int new_node(int i){
	siz[++cnt] = 1;
	id[cnt] = i;
	heap[cnt] = rand();
	return cnt;
}
inline void push_up(int i){
	siz[i] = 1 + siz[lc[i]] + siz[rc[i]];
}
inline int build(int l,int r){
	if(l > r) return 0;
	int mid = l + r >> 1,i = new_node(tmp[mid]);
	lc[i] = build(l,mid - 1);
	rc[i] = build(mid + 1,r);
	push_up(i);
	return i;
}
inline int merge(int x,int y){
	if(!x || !y) return x + y;
	if(heap[x] < heap[y]){
		rc[x] = merge(rc[x],y);
		push_up(x);
		return x;
	} else {
		lc[y] = merge(x,lc[y]);
		push_up(y);
		return y;
	}
}
inline void split(int i,int k,int& x,int& y){
	if(!i) x = y = 0;
	else {
		if(id[i] <= k){
			x = i;
			split(rc[i],k,rc[i],y);
		} else {
			y = i;
			split(lc[i],k,x,lc[i]);
		}
		push_up(i);
	}
}
ll T[maxn];
inline void update(int i,ll x){
	for(;i <= n;i += (i & -i)) T[i] += x;
}
inline ll query(int i){
	ll ret = 0;
	for(;i;i -= (i & -i)) ret += T[i];
	return ret;
}
inline void dfs(int p,int x){
	if(!p) return;
	if(lc[p]) dfs(lc[p],x);
	if(a[id[p]] % x == 0){
		update(id[p],-a[id[p]]);
		a[id[p]] /= x;
		update(id[p],a[id[p]]);
	}
	if(a[id[p]] % x == 0)
		tmp[++len] = id[p];
	if(rc[p]) dfs(rc[p],x);
}
inline void update(int l,int r,int a){
	int x,y,z;
	split(rt[a],r,x,z);
	split(x,l - 1,x,y);
	len = 0;
	dfs(y,a);
	int k = build(1,len);
	rt[a] = merge(merge(x,k),z);
}
inline ll query(int l,int r){
	return query(r) - query(l - 1);
}
signed main(){
	n = Read();
	m = Read();
	for(int i = 1;i <= n;++i){
		a[i] = Read();
		update(i,a[i]);
		for(int j = 1;j * j <= a[i];++j)
			if(a[i] % j == 0){
				value[j].push_back(i);
				if(j * j != a[i]) value[a[i] / j].push_back(i);
			}
	}
	for(int i = 1;i < maxn;++i){
		len = 0;
		for(int j = 0;j < value[i].size();++j) tmp[++len] = value[i][j];
		rt[i] = build(1,len);
	}
	ll last = 0;
	while(m--){
		int opt,l,r,x;
		opt = Read();
		l = Read() ^ last;
		r = Read() ^ last;
		if(opt == 1){
			x = Read() ^ last;
			if(x != 1) update(l,r,x);
		} else printf("%lld\n",last = query(l,r));
	}
	return 0;
}