题目大意：

给定一个长度为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)

解题思路：

线段树+GCD = 正解

GCD 更相减损术 | (扩展)欧几里得算法

都可以

欧几里得算法能过我就用了欧几里得求gcd

t[now].g=gcd(t[leftson].g,t[rightson].g);

询问的答案就是

gcd(a[l],Ask(1,l+1,r));

我发现很多人的写法和我不同，于是我用了一下别人的写法。接着我心里默默地想：再也不用别人的写法了，本来想改，但是我懒我没多少时间去改，反正能AC的就是好代码

Accepted code：

#include
    
     #include
     
      #include
      
       #define ls (now<<1)#define rs ((now<<1)+1)#define ll long longusing namespace std;const int N=5e5+5;const int M=1e5+5;ll a[N],b[N],num[N<<2],s[N<<2];int l[N<<2],r[N<<2],lc[N<<2],rc[N<<2],n,m;//以下装逼部分 inline void read(ll &f) {    char c=getchar();f=0;int ag=1;    while(!isdigit(c)) {
   if (c=='-') ag=-1; c=getchar();}    while(isdigit(c)){f=(f<<3)+(f<<1)+c-48;c=getchar();}    f*=ag; return;}void write(ll x) {    if(x>9) write(x/10);putchar(x%10+48);return;}void writeln(ll x) {    if (x<0) putchar('-'),x*=-1; write(x); putchar('\n'); return;}//以上装逼部分//以下树状数组 void add(int x,ll y) {    for(;x<=n;x+=(x&-x)) s[x]+=y;}ll get(int x) {    ll res=0;    for(;x;x-=(x&-x)) res+=s[x];    return res;}//以上树状数组 //以下GCD ll gcd(ll a,ll b){    return !a?b:gcd(b%a,a);}//以上GCD //以下线段树 //建树来袭 int len=0;void build(int L,int R){    int t=++len;    l[t]=L;r[t]=R;    if(L==R){num[t]=b[L];return;}    int mid=(L+R)>>1;    lc[t]=len+1,build(L,mid);    rc[t]=len+1,build(mid+1,R);    num[t]=gcd(num[lc[t]],num[rc[t]]);}//修改来袭 void change(int now,int x,ll dat) {    if (l[now]==r[now]) {num[now]+=dat;return;}    int mid=(l[now]+r[now])>>1;    if (x<=mid) change(lc[now],x,dat);    else change(rc[now],x,dat);    num[now]=gcd(num[lc[now]],num[rc[now]]);}//询问来袭 ll Ask(int now,int x,int y) {    if (x>y) return 1;    if (l[now]==x&&r[now]==y) return num[now];    int mid=(l[now]+r[now])>>1;    if (y<=mid) return Ask(lc[now],x,y);    else if (x>mid) return Ask(rc[now],x,y);    else    return gcd(Ask(lc[now],x,mid)            ,Ask(rc[now],mid+1,y));}//以上线段树int main() {//  freopen("input","r",stdin);//  freopen("1.txt","w",stdout);    scanf("%d%d",&n,&m);    for (int i=1;i<=n;i++) read(a[i]);    for (int i=1;i<=n;i++) b[i]=a[i+1]-a[i];    add(1,a[1]);    for (int i=2;i<=n;i++) add(i,b[i-1]);    build(1,n-1);    while(m--)    {        char c[2];        scanf("%s",c);        int l,r;        scanf("%d%d",&l,&r);        if(c[0]=='Q')            writeln(abs(gcd(get(l),Ask(1,l,r-1))));        else        {            ll dat; read(dat);            add(l,dat);            if(l>1)change(1,l-1,dat);            if(r