算进 区间最大公因数 单点线段树
https://www.acwing.com/problem/content/247/
题目：
给定一个长度为 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)。
对于每个询问，输出一个整数表示答案。
输入格式：
第一行两个整数 N,M。
第二行 N 个整数 A[i]。
接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。
输出格式：
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围：
N≤500000,M≤100000, 1≤A[i]≤10^{18}, |d|≤10^{18}
样例：
data.1
5 5
1 3 5 7 9
Q 1 5
C 1 5 1
Q 1 5
C 3 3 6
Q 2 4
1
2
4
data.2
5 5
1 3 5 7 9
Q 1 5
C 1 5 1
Q 5 5
C 3 3 6
Q 2 4
1
10
4
思路：
首先区间修改，考虑线段树，分析如何处理怎么维护区间的 gcd，容易想到: gcd(a,b,c)=gcd(gcd(a,b),gcd(b,c)) ，但是由于存在区间修改，我们需要处理如何从 gcd(a,b,c) 推导出 gcd(a+1,b+1,c+1)？结论是利用差分，因为有 gcd(a,b)=gcd(a,b-a)，所以有：
$$<br>gcd(a,b,c) \iff gcd(a,b-a,c-b)<br>$$</div> <br><div id="mathjax-n31" class="mathjax-block md-end-block md-math-block md-rawblock" data-math-tag-before="0" data-math-tag-after="0" data-math-labels="[]">$$<br>gcd(a+1,b+1,c+1)=gcd(a+1,(b+1)-(a+1),(c+1)-(b+1)) \\ \iff gcd(a+1,b-a,c-a)<br>$$</div> <br><p class="md-end-block md-p"><span class="md-plain">容易想到我们需要维护一个支持<span class="md-pair-s "><strong>区间查询、单点修改</strong><span class="md-plain">的<span class="md-pair-s "><strong>差分</strong><span class="md-plain">结构，我们用线段树维护差分。
证明：
证明 gcd(a,b) = gcd(a,b-a)：
令gcd(a,b)=g，所以 \left\{\begin{matrix} a=k_1g \\ b=k_2g \end{matrix}\right. ，且 k_1 与 k_2 互质，所以 b=(k_2-k_1)g，若证 gcd(a,b)=gcd(a,b-a)，即证：gcd(a,b-a)=g=gcd(a,b)，即证：k_1 与 (k_2-k_1) 互质。
假设 k_1 与 (k_2-k_1) 不互质，存在最大公因数 g'，g'≠1，则有：\left\{\begin{matrix} k_1=xg' \\ k_2-k_1=yg' \end{matrix}\right. 。
即 (k_2-k_1)g'+k_1g'=(x+y)g'=k_2，那么有 gcd(k_1,k_2)=g'， g'≠1，则 k_1⊥(k_2-k_1)， 那么有 gcd(a,b-a)=g=gcd(a,b) 成立。
证明 gcd(a,b,c)=gcd(a,b-a,c-b)
用 (a,b) 表示 gcd(a,b)。
$$<br>(a,b,c)\iff((a,b),(b,c))=((a,b-a),(b, c-b))=(a,b-a,b,c-b) \\ \therefore (a,b,c)=((a,b-a,b),c-b) \\ 又\because gcd(a,b)\iff gcd(a,b-a) \\ \therefore (a,b-a,b)=(a,b-a) \\ \therefore (a,b,c)=((a,b-a),c-b)=(a,b-a,c-b)<br>$$</div> <br><h4 class="md-end-block md-heading"><span class="md-pair-s ">实现和细节<span class="md-plain">：线段树 tr 对差分进行维护，我们想要修改原数组中 A[l,r]，都加上d，就相当于在差分数组上 b[l]+=d，b[r+1]-=d，对应线段树就是 modify(1, l, d)，以及 modify(1, r+1, -d)，需要注意比较 r+1 和线段树边界 N 的大小，若 r+1>N ，则直接不需要操作。 由于 gcd(a,b,c)=gcd(a,b-a,c-b)，所以我们需要知道第一个的真实值，即对差分数组求前缀和，对应线段树操作就是 askSum(1,1,l)，并且和 [l+1,r] 求最大公约数 gcd，即 askGcd(1,l+1,r)，因为差分操作使得 gcd 存在负数，则是不符合的，所以输出需要取绝对值。
由数据范围知需要开 long long。
pushup 的实现：
void pushup(seg &u, seg &l, seg &r) {
u.sum = l.sum+r.sum;
u.gcd = __gcd(l.gcd, r.gcd);
}
Coding 时间到
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
constexpr int N = 5e5 + 13;
struct seg{
int l, r;
int sum, gcd;
}tr[N*4];
int n, a[N], b[N];
void pushup(seg &u, seg &l, seg &r) {
u.sum = l.sum+r.sum;
u.gcd = __gcd(l.gcd, r.gcd);
}
void pushup(int u) {
pushup(tr[u], tr[u<<1], tr[u<<1|1]);
}
void build(int u, int l, int r) {
tr[u].l=l, tr[u].r=r;
if (l==r) tr[u].sum=tr[u].gcd=b[l];
else {
int mid=l+r>>1;
build(u<<1, l, mid), build(u<<1|1, mid+1, r);
pushup(u);
}
}
void modify(int u, int pos, int x) {
if (pos == tr[u].l && tr[u].r == pos) {
tr[u].sum += x, tr[u].gcd += x;
} else {
int mid = tr[u].l+tr[u].r>>1;
if (pos <= mid) modify(u<<1, pos, x);
else modify(u<<1|1, pos, x);
pushup(u);
}
}
int askSum(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) {
return tr[u].sum;
}
int mid = tr[u].l+tr[u].r>>1;
int ans = 0;
if (l <= mid) ans+=askSum(u<<1, l, r);
if (r > mid) ans+=askSum(u<<1|1, l, r);
return ans;
}
int askGcd(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) {
return tr[u].gcd;
}
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return askGcd(u<<1, l, r);
else if (l > mid) return askGcd(u<<1|1, l, r);
else return __gcd(askGcd(u<<1,l,r), askGcd(u<<1|1,l,r));
}
int solve()
{
int q; cin >> n >> q;
for (int i=1;i <= n;i ++ ) {
cin>>a[i]; b[i]=a[i]-a[i-1];
}
build(1, 1, N-3);
// for (int i=1;i <= n;i ++ )
// cout<<askSum(1, 1, i)<<" \n"[i==n];
for (int i=1;i <= q;i ++ ) {
string op; cin >> op;
if (op[0] == 'C') {
int l, r, d; cin >> l >> r >> d;
modify(1, l, d);
if (r+1 < N) modify(1, r+1, -d);
} else {
int l, r; cin >> l >> r;
int step = askSum(1, 1, l);
int g = (r-l)?__gcd(step, askGcd(1, l+1, r)):step;
cout << abs(g) << '\n';
}
// cout<<"i:? "<<'\n';
// for (int i=1;i <= n;i ++ )
// cout<<askSum(1,1,i)<<" \n"[i==n];
}
return 1;
}
signed main()
{
cin.tie(0) -> sync_with_stdio(0);
int T(1); //cin>>T;
while (T -- )
solve();
return 0;
}
标签：gcd,int,题解,线段,差分,seg,最大公约数,sum,ACwing From： https://www.cnblogs.com/liyiHuanBlogs/p/17134282.html