[题解] P4435 [COCI2017-2018#2] ​​Garaža

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;
}