题目地址：http://contest-hunter.org:83/contest/0x40%E3%80%8C%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%BF%9B%E9%98%B6%E3%80%8D%E4%BE%8B%E9%A2%98/4302%20Interval%20GCD
描述
给定一个长度为N的数列A，以及M条指令 (N≤5*10^5, M<=10^5)，每条指令可能是以下两种之一：
“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个整数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*10^5，l<=r，数据保证任何时刻序列中的数都是不超过2^62-1的正整数。
分析：
求 gcd 有两种方法：①辗转相除②更相减损术；
那么由二元拓展到三元：
gcd ( x,y,z )= gcd( x,y-x,z-y );
同理拓展到多元，那么我们需要维护一个差分序列B[i]=a[i]-a[i-1]，用线段树加以维护；
1.对于，“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。
B[l]+=d,B[r]-=d;进行两次单点修改就ok了
2.“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。
gcd（a[l],query(1,l+1,r))
注意代码中sum(i)维护的是A[i]的增量，gcd（a[l]+sum(l),query(1,l+1,r))
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define N 500010
#define ll long long
using namespace std;ll a[N],b[N],c[N];
int n,m;struct node //线段树
{int l,r;ll dat;
}tree[N*4];ll gcd(ll a, ll b){return b ? gcd(b, a%b) : a;
}
int lowbit(int x){return x & -x;
}
ll sum(int x){ll sum = 0;while(x){sum += c[x];x -= lowbit(x);}return sum;
}
void add(int x, ll val){while(x <= n){c[x] += val;x += lowbit(x);}
}void PushUp(int x)
{tree[x].dat=gcd(tree[x<<1].dat,tree[x<<1|1].dat);
}
void build(int x,int l,int r) //建树
{tree[x].l=l;tree[x].r=r;if (l==r) //叶子节点{tree[x].dat=b[l];return;}int mid=(l+r)>>1;build(x<<1,l,mid);build(x<<1|1,mid+1,r);PushUp(x);
} ll query(int x,int l,int r) //查找
{ if (l<=tree[x].l&&r>=tree[x].r) return abs(tree[x].dat); //找到int mid=(tree[x].l+tree[x].r)>>1;ll ans=0;if (l<=mid) ans=gcd(ans,query(x<<1,l,r));if (r>mid) ans=gcd(ans,query(x<<1|1,l,r)); return abs(ans);
}void update(int x,int y,ll k) //线段树单点修改
{if (tree[x].l==tree[x].r) {tree[x].dat += k;return ;}int mid=(tree[x].l+tree[x].r)/2;if (y<=mid) update(x<<1,y,k);else update(x<<1|1,y,k);PushUp(x);
}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];}build(1,1,n); char ch[2];while(m--){int l, r;scanf("%s", ch);scanf("%d %d", &l, &r);if(ch[0] == 'C'){ll d;scanf("%lld", &d);update(1, l, d);if(r < n) update(1, r+1, -d);add(l, d);add(r+1, -d);}else{ll al = a[l] + sum(l);printf("%lld\n", gcd(al, query(1,l+1,r)));;}}return 0;
}