Description
Link.
区间查 $x$ 的倍数并除掉，区间查和。
Solution
平衡树。
首先有个基本的想法就是按 $a_{i}$ 开平衡树，即对于每个 $a_{i}$ 都开一棵平衡树，共5e5棵，第 $i$ 棵平衡树维护的值是所有 $a_{i}$ 的倍数在原数组中的下标，用处后面讲。
注意到一个小性质，一个正整数 $A$ 最多被整除 $\log_{2}A$ 次，这个很好想，每次都至少减少一半。可以当成一个 trick 记下来。
整个区间的数最多被除 $\sum_{i=1}^{n}\log_{2}a_{i}$ 次，区间和的操作可以用树状数组操作实现，则整体的操作复杂度为 $\Theta(\sum_{i=1}^{n}\log_{2}a_{i}+\log_{2}a_{i})$。
开头提到了对于每个 $a_{i}$ 我们都开一棵平衡树，作用就体现在这里。因为如果要保证正确的时间复杂度，我们需要快速的找到需要执行操作的数。
这里我采用的是 FHQ-Treap。
我们可以用两次 split 操作在 $x$ 的平衡树中提取出当前的询问区间，由于我们是以下标为平衡树维护的权值，所以我们用按值分裂即可提取出区间。
然后我们就在提取出的子树中 DFS 遍历，然后暴力操作，把操作后依然是 $x$ 的倍数的数记录下来，操作完后用这个数组再建一棵临时树然后和之前 split 出来的子树一起合并回去。
操作之前记得预处理每个数的所有约数，这个简单，直接用 vector 即可。
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <queue>
using namespace std;
typedef long long t_t;
const int Maxn = 1e5 + 5;
const int Maxa = 5e5 + 5;
int n, m, xxx, zip, tot, isa[Maxn], bin[Maxa], root[Maxa];
struct Treap
{
int l, r, key, val;
} t[Maxa * 230];
struct Fenwick_Tree
{
t_t bit[Maxn];
void ins(int x, t_t v)
{
for (; x <= n; x += x & -x) bit[x] += v;
}
t_t sum(int x)
{
t_t ret = 0;
for (; x; x -= x & -x) ret += bit[x];
return ret;
}
} fwt;
vector < int > vec[Maxa];
int newnode(int val)
{
t[++tot].val = val;
t[tot].key = rand();
return tot;
}
void split(int now, int val, int &x, int &y)
{
if (now == 0) x = y = 0;
else
{
if (t[now].val <= val)
{
x = now;
split(t[now].r, val, t[now].r, y);
}
else
{
y = now;
split(t[now].l, val, x, t[now].l);
}
}
}
int merge(int x, int y)
{
if (x == 0 || y == 0) return x | y;
if (t[x].key > t[y].key)
{
t[x].r = merge(t[x].r, y);
return x;
}
else
{
t[y].l = merge(x, t[y].l);
return y;
}
}
int build(int l, int r)
{
if (l > r) return 0;
int mid = (l + r) >> 1;
int now = newnode(bin[mid]);
t[now].l = build(l, mid - 1);
t[now].r = build(mid + 1, r);
return now;
}
void dfs(int now, int val)
{
if (now == 0) return ;
dfs(t[now].l, val);
if (isa[t[now].val] % val == 0)
{
fwt.ins(t[now].val, -isa[t[now].val]);
isa[t[now].val] /= val;
fwt.ins(t[now].val, isa[t[now].val]);
}
if (isa[t[now].val] % val == 0) bin[++zip] = t[now].val;
dfs(t[now].r, val);
}
int tx, ty, tp;
void change(int l, int r, int x)
{
if (x == 1) return ;
split(root[x], r, tx, tp);
split(tx, l - 1, tx, ty);
zip = 0;
dfs(ty, x);
root[x] = merge(tx, merge(build(1, zip), tp));
}
signed main()
{
srand((114514 - 1) / 3 - 4);
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &isa[i]);
fwt.ins(i, isa[i]);
xxx = max(xxx, isa[i]);
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j * j <= isa[i]; ++j)
{
if (isa[i] % j == 0)
{
vec[j].push_back(i);
if (j * j != isa[i]) vec[isa[i] / j].push_back(i);
}
}
}
for (int i = 1; i <= xxx; ++i)
{
zip = 0;
for (unsigned j = 0; j < vec[i].size(); ++j) bin[++zip] = vec[i][j];
root[i] = build(1, zip);
}
for (int i = 0; i < m; ++i)
{
int t, l, r, x;
scanf("%d %d %d", &t, &l, &r);
if (t == 1)
{
scanf("%d", &x);
change(l, r, x);
}
else printf("%lld\n", fwt.sum(r) - fwt.sum(l - 1));
}
return 0;
}