玄关求卡常

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5,maxn = 5e5 + 5;
int n,Q,dat[N],pos[21496900],nxt[21496900],L[maxn],R[maxn],cnt[maxn],tmp_len;
ll lst;
char out_buf[1 << 22],tmp[20];
size_t out_len = 0;
namespace Bit{
	ll sum[N];
	__attribute__((always_inline)) inline void add(int x,int v){
		for(;x <= n;x += x & -x){
			sum[x] += v;
		}
	}
	__attribute__((always_inline)) inline ll query(int x){
		ll res = 0;
		for(;x > 0;x -= x & -x){
			res += sum[x];
		}
		return res;
	}
}
__attribute__((always_inline)) inline char get_char(){
	static char buf[1 << 16],*s = buf,*t = buf;
	if(s == t){
		t = (s = buf) + fread(buf,1,1 << 16,stdin);
		if(s == t){
			return EOF;
		}
	}
	return *s++;
}
__attribute__((always_inline)) inline int read_int(){
	register int x = 0,f = 1;
	char ch = get_char();
	while(ch < '0' or ch > '9'){
		if(ch == '-'){
			f = -1;
		}
		ch = get_char();
	}
	while(ch >= '0' and ch <= '9'){
		x = x * 10 + ch - '0';
		ch = get_char();
	}
	return x * f;
}
__attribute__((always_inline)) inline void write_int(ll x){
	if(x == 0){
		out_buf[out_len ++] = '0';
		out_buf[out_len ++] = '\n';
		return;
	}
	if(x < 0){
		out_buf[out_len ++] = '-';
		x = -x;
	}
	tmp_len = 0;
	while(x > 0){
		tmp[tmp_len ++] = (x % 10ll) + '0';
		x /= 10ll;
	}
	for(register int i = tmp_len - 1;i >= 0;i --){
		out_buf[out_len ++] = tmp[i];
	}
	out_buf[out_len ++] = '\n';
}
inline int get_next(int id,int pos){
	if(pos > R[id] or pos == -1){
		return -1;
	}
	if(nxt[pos] == pos){
		return pos;
	}
	return nxt[pos] = get_next(id,nxt[pos]);
}
__attribute__((always_inline)) inline void del(int id,int pos){
	nxt[pos] = get_next(id,pos + 1);
}
int main(){
	n = read_int();
	Q = read_int();
	for(register int i = 1;i <= n;i ++){
		dat[i] = read_int();
		for(register int j = 1;j * j <= dat[i];j ++){
			div_t res = div(dat[i],j);
			if(res.rem == 0){
				cnt[j] ++;
				register int k = res.quot;
				if(k != j){
					cnt[k] ++;
				}
			}
		}
		Bit::add(i,dat[i]);
	}
	for(register int i = 2;i <= maxn - 5;i ++){
		if(cnt[i] == 0){
			R[i] = R[i - 1];
			continue;
		}
		L[i] = R[i - 1] + 1;
		R[i] = L[i] + cnt[i] - 1;
		for(register int j = L[i];j <= R[i];j ++){
			nxt[j] = j;
		}
	}
	memset(cnt,0,sizeof(cnt));
	for(register int i = 1;i <= n;i ++){
		for(register int j = 1;j * j <= dat[i];j ++){
			div_t res = div(dat[i],j);
			if(res.rem == 0){
				if(j != 1){
					pos[L[j] + (cnt[j] ++)] = i;
				}
				register int k = res.quot;
				if(k != j and k != 1){ 
					pos[L[k] + (cnt[k] ++)] = i;
				}
			}
		}
	}
	while(Q --){
		register int opt,l,r;
		opt = read_int();
		l = read_int();
		r = read_int();
		l ^= lst;
		r ^= lst;
		if(opt == 1){
			register int x;
			x = read_int();
			x ^= lst;
			if(x == 1 or L[x] == 0){
				continue;
			}
			register int pos_l = lower_bound(pos + L[x],pos + R[x] + 1,l) - pos;
			register int pos_r = upper_bound(pos + L[x],pos + R[x] + 1,r) - pos - 1;
			for(register int i = get_next(x,pos_l);i <= pos_r and i != -1;i = get_next(x,i + 1)){
				register int p = pos[i];
				if(dat[p] % x != 0){
					del(x,i);
					continue;
				}
				Bit::add(p,-(dat[p] - dat[p] / x));
				dat[p] /= x;
				if(dat[p] % x != 0){
					del(x,i);
				}
			}
		}else{
			lst = Bit::query(r) - Bit::query(l - 1);
			write_int(lst);
		}
	}
	fwrite(out_buf,1,out_len,stdout);
	return 0;
}