题目描述
给定一个长度为 \(N\) 的数列 \(A\)，以及 \(M\) 条指令，每条指令可能是以下两种之一：
C l r d，表示把 \(A[l],A[l+1],…,A[r]\) 都加上 \(d\)。Q l r，表示询问 \(A[l],A[l+1],…,A[r]\) 的最大公约数(\(GCD\))。
对于每个询问，输出一个整数表示答案。
解题思路
\(\qquad\)区间问题可以用线段树，但是这个既要区间求\(GCD\)又要区间加，怎么办。
\(\qquad\qquad\qquad\qquad\) 这时候老祖宗的智慧就来了
更向减损术的扩展版本
\(\qquad\large gcd(x_0,x_1,x_2,x_3....x_n) = gcd(x_0,x_1-x_0,x_2-x_1.....x_n-x_{n-1})\)
看出了什么，\(\LARGE 差分啊 啊啊啊啊\)
\(\qquad\)刚好差分可以很好地维护前缀和，支持区间修改，所以我们就可以用一颗差分树状数组（区间修改，单点查询）来支持我们的\(1\)操作，然后用一颗支持单点修改，区间查询的线段树来维护区间的\(GCD\)，这样就可以实现我们的区间\(GCD\)查询了。
很重要的注意事项：
\(\qquad\)我们查询的时候需要查询区间\([l,r]\)的区间\(GCD\)，应该用\(a[l]\)和\([l+1,r]\)的区间\(GCD\)再取一个\(GCD\)，为什么？
\(\qquad\)原因如下：
\(\qquad\)\(\qquad\)毕竟我们的\(GCD\)查询是用差分实现的，那么对于每一段区间\([l,r]\)的\(GCD\)，可以用更向减损术这样表示：
\(\quad\large gcd(a_l, a_{l+1}, a_{l+2}...a_{r-1}, a_{r}) = gcd(a_{l},a_{l+1}-a_{l},....a_{r}-a_{r-1})\)
观察上式可以发现，我们后半段的值都是差分值，是可以直接用线段树查询的，但是我们的第一个值都是\(a_l\)，它在线段树中的值是一个差分值\(a_l-a_{l-1}\)，所以这回导致我们的查询操作出问题，所以应该揪出来特殊处理。
然后这题我们可以用树状数组动态维护每个数的值，代码如下
void add(int x, LL v)
{
for (; x <= n; x += x & -x) c[x] += v;
}
LL ask(int x)
{
LL res = 0;
for (; x; x -= x & -x) res += c[x];
return res;
}
在main()函数中：
scanf("%d", &a[i]), add(i, a[i] - a[i - 1]);
代码
#include <iostream>
#include <algorithm>
using namespace std;
using LL = long long;
const int N = 5e5 + 10;
LL a[N], c[N], b[N];
int n, m;
struct Seg
{
int l, r;
LL v;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define v(x) tr[x].v
} tr[N << 2];
void add(int x, LL v)
{
for (; x <= n; x += x & -x) c[x] += v;
}
LL ask(int x)
{
LL res = 0;
for (; x; x -= x & -x) res += c[x];
return res;
}
LL gcd(LL a, LL b)
{
return abs(__gcd(a, b));
}
void build(int p, int l, int r)
{
l(p) = l, r(p) = r;
if (l == r) return void (v(p) = b[l]);
int mid = l + r >> 1;
build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
v(p) = gcd(v(p << 1), v(p << 1 | 1));
}
void modify(int p, int x, LL v)
{
if (l(p) == x && r(p) == x) return void (v(p) += v);
int mid = l(p) + r(p) >> 1;
if (x <= mid) modify(p << 1, x, v);
else modify(p << 1 | 1, x, v);
v(p) = gcd(v(p << 1), v(p << 1 | 1));
}
LL query(int p, int l, int r)
{
if (l(p) >= l && r(p) <= r) return v(p);
int mid = l(p) + r(p) >> 1;
LL v = 0;
if (l <= mid) v = gcd(v, query(p << 1, l, r));
if (r > mid) v = gcd(v, query(p << 1 | 1, l, r));
return v;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
scanf("%lld", &a[i]), b[i] = a[i] - a[i - 1], add(i, b[i]);
build(1, 1, n);
while (m -- )
{
char op[2]; int l, r;
scanf("%s%d%d", op, &l, &r);
if (op[0] == 'C')
{
LL d; scanf("%lld", &d);
modify(1, l, d);
if (r < n) modify(1, r + 1, -d);
add(l, d), add(r + 1, -d);
}
else {
LL res = l < r ? query(1, l, r) : 0;
printf("%lld\n", res);
}
}
return 0;
}