洛谷 P10463 Interval GCD Solution

Description

给定序列 $a=(a_1,a_2,\cdots ,a_n)$，有 $m$ 个操作分两种：

• $\mathrm{add}(l,r,k)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow a_i+k$.
• $\mathrm{query}(l,r)$：求 $|\gcd (a_l,a_{l+1},\cdots ,a_r)|$.

Limitations

$1\le n\le 5\times 10^5$
$1\le m\le 10^5$
$1\le a_i\le 10^{18}$
$|k|\le 10^{18}$
任意时刻所有数均在 $2^{63}$ 以内.
$1\text{s},512\text{MB}$

Solution

区间加区间 $\gcd$ 不太好做，考虑转化成单点加.
首先要知道一条性质：$\gcd (x,y)=\gcd (x,y-x)$.
那么就可以推式子了：
$$\begin{array}{rl}& gcd(a_l,a_{l+1},\cdots ,a_r)\\ & =gcd(a_l,a_{l+1}-a_l,a_{l+1},a_{l+2}-a_{l+1},\cdots ,a_r,a_r-a_{r-1})\\ & =gcd(a_l,a_{l+1}-a_l,a_{l+2}-a_{l+1},\cdots ,a_r-a_{r-1})\end{array}$$
发现这就是差分，所以把差分数组拿到线段树上维护，就只需要单点加了.
用树状数组维护一下 $a_l$ 即可，注意答案要 abs.

Code

$2.96\text{KB},686\text{ms},42.48\text{MB}\text{(in total, C++20 with O2)}$

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}

int lowbit(int x){
	return x & -x;
}

template<class T>
struct fenwick{
	int n;
	vector<T> c;
	
	fenwick() {}
	fenwick(int _n): n(_n){
		c.resize(n + 1);
	}
	
	fenwick(const vector<T> &a): n(a.size()){
		c.resize(n + 1);
		for(int i = 1; i <= n; i++){
			c[i] = c[i] + a[i - 1];
			int j = i + lowbit(i);
			if(j <= n) c[j] = c[j] + c[i];
		}
	}
	
	void add(int x, const T& v){
		for(int i = x + 1; i <= n; i += lowbit(i)) c[i] = c[i] + v;
	}
	
	T ask(int x){
		T ans{};
		for(int i = x + 1; i; i -= lowbit(i)) ans = ans + c[i];
		return ans;
	}
	
	T ask(int l, int r){
		return ask(r) - ask(l - 1);
	}
};

namespace seg_tree {
	inline int ls(int u) { return 2 * u + 1; }
	inline int rs(int u) { return 2 * u + 2; }
	
	struct Node {
		int l, r;
		i64 val;
	};
	
	struct SegTree {
		vector<Node> tr;
		inline SegTree() {}
		inline SegTree(const vector<i64>& a) {
			const int n = a.size();
			tr.resize(n << 2);
			build(0, 0, n - 1, a);
		}
		
		inline void pushup(int u) {
			tr[u].val = ::gcd(tr[ls(u)].val, tr[rs(u)].val);
		}
		
		inline void build(int u, int l, int r, const vector<i64>& a) {
			tr[u].l = l, tr[u].r = r;
			if (l == r) {
				tr[u].val = a[l];
				return;
			}
			const int mid = (l + r) >> 1;
			build(ls(u), l, mid, a);
			build(rs(u), mid + 1, r, a);
			pushup(u);
		}
		
		inline void add(int u, int p, i64 x) {
			if (tr[u].l == tr[u].r) {
				tr[u].val += x;
				return;
			}
			const int mid = (tr[u].l + tr[u].r) >> 1;
			if (p <= mid) add(ls(u), p, x);
			else add(rs(u), p, x);
			pushup(u);
		}
		
		inline i64 gcd(int u, int l, int r) {
			if (l <= tr[u].l && tr[u].r <= r) return llabs(tr[u].val);
			const int mid = (tr[u].l + tr[u].r) >> 1;
			i64 res = 0;
			if (l <= mid) res = ::gcd(res, gcd(ls(u), l, r));
			if (r > mid) res = ::gcd(res, gcd(rs(u), l, r));
			return llabs(res);
		}
	};
}
using seg_tree::SegTree;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int n, m;
	cin >> n >> m;
	
	vector<i64> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	
	auto [fwk, sgt] = [&]() {
		vector<i64> b(n);
		adjacent_difference(a.begin(), a.end(), b.begin());
		return make_pair(fenwick<i64>(b), SegTree(b));
	}();
	
	auto query = [&](int l, int r) {
		return gcd(fwk.ask(l), (l < r ? sgt.gcd(0, l + 1, r) : 0LL));
	};
	auto add = [&](int l, int r, i64 v) {
		fwk.add(l, v), sgt.add(0, l, v);
		if (r + 1 < n) fwk.add(r + 1, -v), sgt.add(0, r + 1, -v);
	};
	
	for (int i = 0; i < m; i++) {
		char op; int l, r; i64 v;
		cin >> op >> l >> r, l--, r--;
		if (op == 'C') add(l, r, (cin >> v, v));
		else cout << query(l, r) << endl;
	}
	
	return 0;
}