Description
一个长为 (n) 的非负整数序列 (a)，支持以下两个操作：
1 l r x：把区间 ([l,r]) 中所有 (x) 的倍数除以 (x)。2 l r：查询区间 ([l,r]) 的和。
本题强制在线，每次的 (l,r,x) 需要 (oplus) 上上次答案，如果之前没有询问，则上次答案为 (0)。
Hint
(1le n, mle 10^5)
(0le a_i le 5 imes 10^5)
Solution 1
可以发现全局真正有效的修改的次数并不多。当一个数除上自己的某一个约数是，至少会减少一半。所以这个数列的总 有效 修改次数不会超过 (O(sum_{i = 1}^nlog a_i)) 次。发现第二个操作是区间和，不难想到用树状数组维护。执行 有效 的修改的复杂度为 (O(log n imessumlog a_i))。
但是我们需要面对现实，即如何快速找到需要修改的位置，否则上面都是扯淡。我们发现 (a_i le 5 imes 10^5) ，不是特别大，于是自然而然的从这上面入手。
我们开 (5 imes 10^5) 颗平衡树（FHQ-Treap 或 Splay Tree，这里用了前者），第 (i) 个平衡树存 数列 (a) 中出现过 (i) 的倍数的 下标。
这样就好办了，当修改 ((l, r, x)) 时， 我们把第 (x) 颗平衡树中 在 ([l, r]) 中的元素提取（split）出来作为一个子树，然后在这个子树上…… 暴力Dfs ！
修改后，如果这个数已经不是 (x) 的约数的，就不用再保留这个数了。最后子树重建即可。
约数的话，每个数字可以在根号复杂度下，处理出下标的 vector，详见代码。
-
时间复杂度：(O(sumsqrt{a_i} + log n imessumlog a_i + mlog n))
-
空间复杂度：(O(sum D(a_i)))，(D(x)) 为 (x) 的约数个数。
卡常技巧：
- 快读快写。
- FHQ-Treap 可以不用带
size，由于应用特殊。 改一改。srand的种子
Code for solution 1
不保证每次测评都 AC。
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Problem : Luogu P5610 [Ynoi2013]大学
*/
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
struct IO {
static const int S=1<<21;
char buf[S],*p1,*p2;int st[105],Top;
~IO(){clear();}
inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
IO&operator >> (char&x){while(x=gc(),x==' '||x=='
');return *this;}
template<typename T> IO&operator >> (T&x){
x=0;bool f=0;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
f?x=-x:0;return *this;
}
IO&operator << (const char c){pc(c);return *this;}
template<typename T> IO&operator << (T x){
if(x<0) pc('-'),x=-x;
do{st[++st[0]]=x%10,x/=10;}while(x);
while(st[0]) pc('0'+st[st[0]--]);return *this;
}
} fin, fout;
const int N = 1e5 + 5;
const int MaxA = 5e5 + 5;
const int D = 212;
typedef long long llint;
vector<int> factor[MaxA];
int n, q, a[N];
namespace bit {
llint t[N];
inline void inc(int p, llint v) {
for (; p <= n; p += (p & (-p))) t[p] += v;
}
inline llint sum(int p) {
llint ret = 0;
for (; p; p -= (p & (-p))) ret += t[p];
return ret;
}
};
namespace FHQ_Treap {
const int S = MaxA * D;
int root[MaxA];
struct Node {
int lc, rc;
int value;
int priority;
inline Node() { }
inline Node(int val) : value(val) {
priority = rand();
lc = rc = 0;
}
} t[S];
int total = 0;
void split(int u, int k, int& l, int& r) {
if (!u) return void(l = r = 0);
if (t[u].value <= k) l = u, split(t[u].rc, k, t[u].rc, r);
else r = u, split(t[u].lc, k, l, t[u].lc);
return ;
}
int merge(int u, int v) {
if (!u || !v) return u | v;
if (t[u].priority > t[v].priority) {
t[u].rc = merge(t[u].rc, v);
return u;
} else {
t[v].lc = merge(u, t[v].lc);
return v;
}
}
int buf[MaxA], top;
int build(int l, int r) {
if (l > r) return 0;
int rt = ++total, mid = (l + r) >> 1;
t[rt] = Node(buf[mid]);
t[rt].lc = build(l, mid - 1);
t[rt].rc = build(mid + 1, r);
return rt;
}
inline void init(int tr, vector<int>& f) {
top = 0;
for (vector<int>::iterator it = f.begin(); it != f.end(); ++it)
buf[++top] = *it;
root[tr] = build(1, top);
}
void travel(int rt, int x) {
if (!rt) return;
travel(t[rt].lc, x);
if (a[t[rt].value] % x == 0) {
bit::inc(t[rt].value, -a[t[rt].value]);
a[t[rt].value] /= x;
bit::inc(t[rt].value, a[t[rt].value]);
}
if (a[t[rt].value] % x == 0)
buf[++top] = t[rt].value;
travel(t[rt].rc, x);
}
};
inline void modify(int l, int r, int x) {
if (x == 1) return;
using namespace FHQ_Treap;
int tx, ty, tp;
split(root[x], r, tx, ty);
split(tx, l - 1, tx, tp);
top = 0, travel(tp, x);
root[x] = merge(tx, merge(build(1, top), ty));
}
signed main() {
srand(3241147);
fin >> n >> q;
int m = 0;
for (register int i = 1; i <= n; i++) {
fin >> a[i], bit::inc(i, a[i]);
m = max(m, a[i]);
for (register int j = 1; j * j <= a[i]; j++)
if (a[i] % j == 0) {
factor[j].push_back(i);
if (j * j != a[i])
factor[a[i] / j].push_back(i);
}
}
for (register int i = 1; i <= m; i++)
FHQ_Treap::init(i, factor[i]);
for (llint lastans = 0; q; --q) {
llint l, r, x, cmd;
fin >> cmd >> l >> r;
l ^= lastans, r ^= lastans;
if (cmd == 1) {
fin >> x, x ^=lastans;
modify(l, r, x);
} else {
lastans = bit::sum(r) - bit::sum(l - 1);
fout << lastans << '
';
}
}
}
Solution 2
和 sol 1 不同的地方是找符合要求的位置还有那些。上面用平衡树维护，但其实可以用 并查集 的思想。
总之就是用一个辅助数组（类似并查集的 father），表示某一个位置接下来应该跳到什么位置。删去时直接在这个辅助数组上改即可，实际上就是对 vector 中 erase 的一个优化（应该）。
具体地，就是对于询问 ((l, r, x)) ，在 (x) 的约数下标列表中找到第一个 (ge l) 的元素 (p)，并且将 (p) 沿着并查集辅助数组跳到最后面没有被移除的哪一个。然后做的时候也像下一次这样跳。发现一个改完不再是 (x) 的约数是，将辅助数组的这个位置（(i)） 设为 (i + 1) 就行。
比上面那个好像（好像）。
Code for solution 2
不卡常，非常舒适。
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Problem : Luogu P5610 [Ynoi2013]大学
*/
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
const int N = 1e5 + 5;
const int MaxA = 5e5 + 5;
typedef long long llint;
int a[N], q, n;
namespace bit {
llint t[N];
inline void inc(int p, llint v) {
for (; p <= n; p += (p & (-p))) t[p] += v;
}
inline llint sum(int p) {
llint ret = 0;
for (; p; p -= (p & (-p))) ret += t[p];
return ret;
}
};
vector<int> factor[MaxA];
vector<int> uset[MaxA];
int find(int k, int x) {
if (x == uset[k].size()) return x;
return (x == uset[k][x]) ? x : uset[k][x] = find(k, uset[k][x]);
}
inline void modify(int l, int r, int x) {
if (x == 1) return;
int p = find(x, lower_bound(factor[x].begin(), factor[x].end(), l) - factor[x].begin());
for (; p < uset[x].size() && factor[x][p] <= r; p = find(x, p + 1)) {
if (a[factor[x][p]] % x == 0) {
bit::inc(factor[x][p], -a[factor[x][p]]);
a[factor[x][p]] /= x;
bit::inc(factor[x][p], a[factor[x][p]]);
}
if (a[factor[x][p]] % x != 0)
uset[x][p] = p + 1;
}
}
signed main() {
ios::sync_with_stdio(false);
cin >> n >> q;
for (register int i = 1; i <= n; i++) {
cin >> a[i], bit::inc(i, a[i]);
for (register int j = 1; j * j <= a[i]; j++)
if (a[i] % j == 0) {
factor[j].push_back(i), uset[j].push_back(uset[j].size());
if (j * j != a[i])
factor[a[i] / j].push_back(i), uset[a[i] / j].push_back(uset[a[i] / j].size());
}
}
for (llint lastans = 0; q; --q) {
llint l, r, x; int cmd;
cin >> cmd >> l >> r;
l ^= lastans, r ^= lastans;
if (cmd == 1) {
cin >> x, x ^= lastans;
modify(l, r, x);
} else {
lastans = bit::sum(r) - bit::sum(l - 1);
cout << lastans << endl;
}
}
return 0;
}