线段树用于解决区间内最大公约数的问题

AcWing 246. 区间最大公约数

题目描述

设有一个长度为 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≤5×10^5,M≤10^5, 1≤A[i]≤10^{18}, |d|≤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