Ynoi二血（

$\texttt{Desciption}$

这题题面友好，直接看题面

$\texttt{Solution}$

考虑到一个数的质因数个数最多不会超过 $O(logn)$ 个，因此除法最多只会执行 $O(nlogn)$ 次。

那么如何找出一段区间内能被 $x$ 整除的数呢？

把一开始所有能被 $x$ 整除的数放到一个数据结构 $s_x$ 中，这个数据结构里面从小到大存储着这些一开始能被 $x$ 整除的数的下标。每次我们需要查询lower_bound（查询第一个下标大于等于 $l$ 的位置），删除（有可能这个数一开始能被整除但除着除着就变了，比如 $20$ 能被 $2$ 整除，但 $20$ 除了 $4$ 后就不能了）。

~~作为一个不会写平衡树的智障，我……~~

貌似我见过这种套路，大概是用一个并查集维护它后面（包括它自己）距离它最近的没被删除的位置。每删除 $i$ 位置，$fa_i=find(i+1)$ 即可。

然后用BIT维护区间和即可。注意维护原始的 $a$ 数组。

时间复杂度？不好说，大概 $O(n\sqrt{n}+nlogn+mlogn)$？

于是你愉快的被卡常卡成66……

优化卡常：

~~卡常指导：monsters谔谔神犇~~

众所周知，由乃题应该先打fread再打正解。
你会发现 $O(n\sqrt{n})$ 的复杂度非常的不优秀，于是改为桶+筛法分解质因数。
你会发现这样需要对下标排序。但是一排序反而越来越慢，因此我们在每次操作的时候再排序，用一个 $vis$ 数组记录是否排过序。
你会发现还是会T，所以我们排序的时候判断一下顺序，如果已经是顺序了那么就不用排序了。
用vector还想过Ynoi？手写内存池即可。
最后，反正我的代码到这里就过了，如果你还是T，建议手动二分内存池大小。

$\texttt{Code}$

#include <cstdio>
#include <vector>
#include <algorithm>
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 65536, stdin), p1 == p2) ? EOF : *p1 ++)

char buf[65536], *p1, *p2;
inline int read()  {
	char ch;
	int x(0);
	while ((ch = gc) < 48);
	do x = x * 10 + ch - 48; while ((ch = gc) >= 48);
	return x;
}

const int N = 500005;
inline int max(const int x, const int y) {return x > y ? x : y;}

int a[N], mem[45000005], tot, n;
struct Vector {
	int stpos, endpos;
	inline void push_back(const int x) {
		stpos ? mem[endpos = ++ tot] = x : mem[stpos = endpos = ++ tot] = x;
	}
	inline int& operator [] (const int x) const {return mem[stpos + x];}
	inline int* begin() {return mem + stpos;}
	inline int *end() {return mem + endpos + 1;}
	inline int size() {return stpos ? endpos - stpos + 1 : 0;}
	inline bool empty() {return !stpos;}
};
long long c[N];
std::vector<int> cnt[N];
bool vis[N];
inline void update(const long long x, const long long d) {
	for (int i(x); i <= n; i += (i & ~i + 1)) c[i] += d;
}
inline long long query(const int x) {
	long long sum(0LL);
	for (int i(x); i; i -= (i & ~i + 1)) sum += c[i];
	return sum;
}

struct Reap {
	Vector fac, fa;
	int find(const int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
	inline void upd(const int l, const int r, const int x) {
		if (!vis[x]) {
			vis[x] = true;
			if (fac.size()) {
				bool flag(0);
				for (int i(0); i < fac.size() - 1; ++ i)
				if (fac[i] > fac[i + 1]) {flag = 1; break;}
				if (flag) std::sort(fac.begin(), fac.end());
			}
			else return;
			for (int i(0); i <= fac.size(); ++ i) fa.push_back(i);
		}
		if (fac.empty()) return;
		int i(find(std::lower_bound(fac.begin(), fac.end(), l) - fac.begin()));
		while (i < fac.size() && fac[i] <= r) {
			if (a[fac[i]] % x) fa[i] = find(i + 1);
			else update(fac[i], a[fac[i]] / x - a[fac[i]]), a[fac[i]] /= x;
			i = find(i + 1);
		}
	}
} s[N];

int main() {
	int m, t(0);
	long long last(0LL);
	n = read(), m = read();
	for (int i(1); i <= n; ++ i)
		t = max(t, a[i] = read()), update(i, a[i]), cnt[a[i]].push_back(i);
	for (int i(2); i <= t; ++ i)
		for (int j(i); j <= t; j += i)
			for (auto k : cnt[j]) s[i].fac.push_back(k);
	while (m --) {
		int op(read()), l(read() ^ last), r(read() ^ last), x;
		if (op == 1) {
			x = read() ^ last;
			if (x != 1) s[x].upd(l, r, x);
		}
		else printf("%lld\n", last = query(r) - query(l - 1));
	}
}

zqs`s blog

洛谷P5610题解

$\texttt{Desciption}$

$\texttt{Solution}$

优化卡常：

$\texttt{Code}$