<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

给定一个长度为 $N$ 的数列 $A$，以及 $M$ 条指令，每条指令可能是以下两种之一：

1. C l r d，表示把 $A\[l\],A\[l+1\],…,A\[r\]$ 都加上 $d$。
2. Q l r，表示询问 $A\[l\],A\[l+1\],…,A\[r\]$ 的最大公约数($GCD$)。

对于每个询问，输出一个整数表示答案。

输入格式

第一行两个整数 $N,M$。

第二行 $N$ 个整数 $A\[i\]$。

接下来 $M$ 行表示 $M$ 条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

$N \\le 500000, M \\le 100000$,
$1 \\le A\[i\] \\le 10^{18}$,
$|d| \\le 10^{18}$

输入样例：

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

思路

如果不懂线段树就看线段树详解（超详细）
这道题就是区间修改和单点查询区间最大公约数。
那我们该怎么做呢？
我们把区间修改和单点查询经过差分转化，让它变成单点修改和区间查询。
这里我们需要知道$\gcd{\{a,b\}}=\gcd{\{a,a-b\}}$，变化一下这个柿子，发现$\gcd{\{a,b,c\}}$就是$\gcd{\{\gcd{\{a,b\}},\gcd{\{b,c\}}\}}$，也就是$\gcd{\{a,b-a,c-a\}}$。相信细心的同学们已经发现，以下规律：$\gcd{\{a_1,a_2,\dots,a_n\}}=\gcd{\{a_1,a_2-a_1,\dots,a_n-a_{n-1}\}}$
最后查询时要注意，代码中第$i$个数的$d$是指$a_i-a_{i-1}$，所以当我们查询$[l,r]$的区间最大公约数时，我们要用$[l+1,r]$的$\gcd$和$a_l$求最大公约数。

代码

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 500010;
int n,m;
LL a[N];
struct segment_tree_node {
    int l,r;
    LL sum,d;
}tr[4 * N];
LL gcd (LL a,LL b) {
    return b ? gcd (b,a % b) : a;
}
void push_up (segment_tree_node &root,segment_tree_node &left,segment_tree_node &right) {
    root.sum = left.sum + right.sum;
    root.d = gcd (left.d,right.d);
}
void push_up (int u) {
    push_up (tr[u],tr[u << 1],tr[u << 1 | 1]);
}
void build_segment_tree (int u,int l,int r) {
    if (l == r) {
        LL b = a[l] - a[l - 1];
        tr[u] = {l,r,b,b};
    }
    else {
        tr[u].l = l,tr[u].r = r;
        int mid = l + r >> 1;
        build_segment_tree (u * 2,l,mid),build_segment_tree (u * 2 + 1,mid + 1,r);
        push_up (u);
    }
}
void modify (int u,int x,LL d) {
    if (tr[u].l == x && tr[u].r == x) {
        LL b = tr[u].sum + d;
        tr[u] = {x,x,b,b};
    }
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify (u * 2,x,d);
        else modify (u * 2 + 1,x,d);
        push_up (u);
    }
}
segment_tree_node query (int u,int l,int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query (u * 2,l,r);
        else if (l > mid) return query (u * 2 + 1,l,r);
        else {
            segment_tree_node left = query (u * 2,l,r);
            segment_tree_node right = query (u * 2 + 1,l,r);
            segment_tree_node ans;
            push_up (ans,left,right);
            return ans;
        }
    }
}
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i];
    build_segment_tree (1,1,n);
    while (m--) {
        char ch;
        int l,r;
        LL d;
        cin >> ch >> l >> r;
        if (ch == 'C') {
            cin >> d;
            modify (1,l,d);
            if (r + 1 <= n) modify (1,r + 1,- d); 
        }
        else {
            segment_tree_node left = query (1,1,l),right ({0,0,0,0});
            if (l + 1 <= r) right = query (1,l + 1,r);
            cout << abs (gcd (left.sum,right.d)) << endl;   //gcd (原序列中第l个数,[l+1,r]的d)
        }
    }
    return 0;
}