Description

給定序列 $a=(a_1,a_2,?,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},?,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},?,a_r)\\ & =gcd(a_l,a_{l+1}?a_l,a_{l+1},a_{l+2}?a_{l+1},?,a_r,a_r?a_{r?1})\\ & =gcd(a_l,a_{l+1}?a_l,a_{l+2}?a_{l+1},?,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;
}