【题目】

传送门

题目描述：

给定一个长度为 n 的数列 a，以及 m 条指令 (n≤5×105,m≤105)，每条指令可能是以下两种之一：

“Clrd”，表示把 al​,al+1​,…,ar​ 都加上 d。
“Qlr”，表示询问 al​,al+1​,…,ar​ 的最大公约数 (gcd)。

输入格式：

第一行两个整数 n,m，第二行 n 个整数 ai​，接下来 m 行每条指令的格式如题目描述所示。

输出格式：

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

样例数据：

输入
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

数据范围与约定：

n,m≤2×105，l≤r，数据保证任何时刻序列中的数都是不超过 262−1的正整数。

【分析】

数据范围为什么都不统一啊。。。

做这道题之前，要先知道一个东西，叫做辗转相减法

有一个关于它的推论，即 gcd(x,y,z)=gcd(x,y−x,z−y)，推广到 n 个数也成立

这里还是简单证一下（如果有错请提出来）
假设 gcd(x,y,z)=a，那么必有互质的三个数 m1​,m2​,m3​ 使 x=m1​a,y=m2​a,z=m3​a
那么 gcd(x,y−x,z−y)=gcd(m1​a,(m2​−m1​)a,(m3​−m2​)a)
由于 m1​,m2​,m3​ 互质，所以 m1​,m2​−m1​,m3​−m2​ 必然也互质，所以 gcd(x,y−x,z−y)=a=gcd(x,y,z)

那么，知道了这个之后又有什么用呢

我们可以用差分的思想，把原数组变为 a1​,a2​−a1​,a3​−a2​,…,an​−an−1​（用 sumi​ 表示 ai​−ai−1​）

这样的话，修改就好办了，直接在 suml​ 加 d，在 sumr+1​ 减 d（中间的数加的 d 相互抵消了）

查询的时候，根据辗转相减法，先找出 gcd(suml+1​,suml+2​,…,sum@font-face { font-family: "autolinktags"; src: url("https://www.seowoai.com/zb_users/plugin/AutoLinkTags/style/fonts/iconfont.woff2") format("woff2"), url("https://www.seowoai.com/zb_users/plugin/AutoLinkTags/style/fonts/iconfont.woff") format("woff"), url("https://www.seowoai.com/zb_users/plugin/AutoLinkTags/style/fonts/iconfont.ttf") format("truetype"); font-weight:normal; font-style:normal; }.tagslink::after { content:"\e613"; margin:2px 0 0 0px; font-size:12px; font-family:"autolinktags"; display:inline-block; vertical-align:top; }