P4435 [COCI2017-2018#2] Garaža
给你一个长度为 \(n\) 的序列 \(a\)，单点改，查询区间 \(\gcd\) 不为 1 的子区间个数。
\(n, Q \le 10^5, a_i \le 10^9\)。
先看单次全局查询怎么做。考虑一个分治，每次我们要计算跨过分治中心 \(mid\) 的答案。因为这个是单调的，所以可以双指针做一下。
再加上修改和区间询问，可以把这个分治结构扔到线段树上去维护。但是这个 push_up 是 \(O(n)\) 的，我们需要更快速的 push_up。对于这个有一个经典结论，就是 \(\gcd\) 最多变化 \(\log\) 次，所以可以直接开一个 vector 把每个 gcd 的连续段存下来，这样 push_up 就是 \(O(\log V)\) 的了，求 \(\gcd\) 的复杂度可以被势能分析掉。
时间复杂度 \(O(n \log n \log V)\)。
constexpr int MAXN = 1e5 + 9;
int n, q, a[MAXN];
int Gcd(int a, int b) {
int az = __builtin_ctz(a), bz = __builtin_ctz(b), z = min(az, bz), t; b >>= bz;
while (a) a >>= az, t = a - b, az = __builtin_ctz(t), b = min(a, b), a = (t < 0 ? (~t + 1) : t);
return b << z;
}
struct Node {
vector<pii> pre, suf;
ll ans;
Node(): ans(0) { pre.clear(), suf.clear(); return; }
friend Node operator + (const Node &x, const Node &y) {
assert(x.pre.size() && x.suf.size() && y.pre.size() && y.suf.size());
Node ans; ans.ans = x.ans + y.ans;
{
int i = 0, j = y.pre.size() - 1, len = 0;
for (auto [g, l] : y.pre) len += l;
for (; i < x.suf.size(); i ++) {
while (j >= 0 && Gcd(x.suf[i].fir, y.pre[j].fir) == 1)
len -= y.pre[j].sec, j --;
ans.ans += 1ll * x.suf[i].sec * len;
}
}
ans.pre = x.pre, ans.suf = y.suf;
int val = ans.pre.back().fir;
for (auto [g, l] : y.pre)
if (Gcd(val, g) == val) ans.pre.back().sec += l;
else ans.pre.emplace_back(val = Gcd(val, g), l);
val = ans.suf.back().fir;
for (auto [g, l] : x.suf)
if (Gcd(val, g) == val) ans.suf.back().sec += l;
else ans.suf.emplace_back(val = Gcd(val, g), l);
return ans;
}
} sgt[MAXN << 2];
void Push_Up(int p) {
sgt[p] = sgt[p << 1] + sgt[p << 1 | 1];
return;
}
void Build(int p = 1, int L = 1, int R = n) {
if (L == R) {
sgt[p] = Node();
sgt[p].pre.emplace_back(a[L], 1);
sgt[p].suf.emplace_back(a[L], 1);
sgt[p].ans = (a[L] != 1);
return;
}
int Mid = L + R >> 1;
Build(p << 1, L, Mid), Build(p << 1 | 1, Mid + 1, R);
Push_Up(p); return;
}
void Update(int pos, int k, int p = 1, int L = 1, int R = n) {
if (L == R) {
sgt[p] = Node();
sgt[p].pre.emplace_back(k, 1);
sgt[p].suf.emplace_back(k, 1);
sgt[p].ans = (k != 1);
return;
}
int Mid = L + R >> 1;
if (pos <= Mid) Update(pos, k, p << 1, L, Mid);
else Update(pos, k, p << 1 | 1, Mid + 1, R);
Push_Up(p); return;
}
Node Query(int l, int r, int p = 1, int L = 1, int R = n) {
if (l <= L && R <= r) return sgt[p];
int Mid = L + R >> 1;
if (r <= Mid) return Query(l, r, p << 1, L, Mid);
if (Mid < l) return Query(l, r, p << 1 | 1, Mid + 1, R);
return Query(l, r, p << 1, L, Mid) + Query(l, r, p << 1 | 1, Mid + 1, R);
}
void slv() {
n = Read<int>(), q = Read<int>();
for (int i = 1; i <= n; i ++) a[i] = Read<int>();
Build();
while (q --) {
int opt = Read<int>();
if (opt == 1) {
int pos = Read<int>(), v = Read<int>();
Update(pos, v);
} else {
int l = Read<int>(), r = Read<int>();
Write(Query(l, r).ans, '\n');
}
}
return;
}