RT，$48 \operatorname{pts}$ 求卡常 /kel

代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;

int a[100007];
ll tree[100007];
vector<int> v1[500007], v2[500007];

inline int lowbit(int x){
	return x & (-x);
}

inline void update(int n, int x, int k){
	while (x <= n){
		tree[x] += k;
		x += lowbit(x);
	}
}

int get_root(int b, int x){
	if (x == v2[b].size() || x == v2[b][x]) return x;
	return v2[b][x] = get_root(b, v2[b][x]);
}

inline ll get_sum(int x){
	register ll ans = 0;
	while (x > 0){
		ans += tree[x];
		x -= lowbit(x);
	}
	return ans;
}

int main(){
	register int n, m, k;
	register ll last_ans = 0;
	cin >> n >> m;
	for (register int i = 1; i <= n; i++){
		cin >> a[i];
		k = max(k, a[i]);
		update(n, i, a[i]);
	}
	for (register int i = 1; i <= n; i++){
		register int t = sqrt(a[i]);
		for (register int j = 1; j <= t; j++){
			if (a[i] % j == 0){
				v1[j].push_back(i);
				v2[j].push_back(v2[j].size());
				if (j * j != a[i]){
					v1[a[i] / j].push_back(i);
					v2[a[i] / j].push_back(v2[a[i] / j].size());
				}
			}
		}
	}
	for (register int i = 1; i <= m; i++){
		register int op;
		register ll l, r;
		cin >> op >> l >> r;
		l ^= last_ans;
		r ^= last_ans;
		if (op == 1){
			ll x;
			cin >> x;
			x ^= last_ans;
			if (x == 1) continue;
			register int size = v1[x].size();
			for (register int j = get_root(x, lower_bound(v1[x].begin(), v1[x].end(), l) - v1[x].begin()); j < size && v1[x][j] <= r; j = get_root(x, j + 1)){
				int t = v1[x][j];
				if (a[t] % x == 0){
					update(n, t, a[t] / x - a[t]);
					a[t] /= x;
				}
				if (a[t] % x != 0){
					v2[x][j] = j + 1;
				}
			}
		} else {
			last_ans = get_sum(r) - get_sum(l - 1);
			cout << last_ans << endl;
		}
	}
	return 0;
}