【题目】

给定一个长度为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)。
对于每个询问，输出一个整数表示答案。

【题解】

这道题十分的迷，没有给输入的数据范围。而经过测试后，输入的数居然是超int的?!。这其实是很难受得一件事情，因为只要有代码洁癖或者没遇到这种普通输入数就开的，再加上这个很明显是线段树的，并且N又看上去挺大的，这第一次做的时候，肯定会用int的，然后就GG了。
核心的做法其实就是围绕"《九章算术》之更相减损术"的理论来进行计算的，那如果按照这个理论的话，我们就可以线段树去维护两个数的差，而在其中可以利用差分的思想，即如果要更新区间内的点的话，我们只需要更新点，然后再是更新点即可，不理解的话，可以自己草稿纸上算一下：维护两个数的差，如果改变其中原本区间内的数，其实只有维护的数里面、两点的值会进行改变。除了线段树最低层的单点是维护差值，其它则是维护最大公约数。即。然后就能得到这道题的整体做法，即线段树单点更新差值，区间查找最大公约数，然后线段树维护或者树状数组维护原本数的值（建议用树状数组配合差值的性质，变相求出单点的值，做区间更新和单点查找的操作(这一部分看不懂的话，可以结合下面的代码理解下)）。然后最终输出的答案就是。
(按道理来说是不会爆内存的，但就我来说，每次交，浮动还是挺大的，最大最小相差10000多，这我就很无语，导致有时过，有时不过的，所以如果觉得自己做法肯定没问题的，建议多交几次。。。)

时间复杂度：

#include<iostream>
#include<cstring>
#include<sstream>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#define fi first
#define se second
#define MP make_pair
#define P pair<int,int>
#define PLL pair<ll,ll>
#define Sca(x) scanf("%d",&x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%ld",&x)
#define Scll(x) scanf("%lld",&x)
#define Pri(x) printf("%d\n",x);
#define Prl(x) printf("%lld\n",x);
#define For(i,x,y) for(int i=x;i<=y;i++)
#define _For(i,x,y) for(int i=x;i>=y;i--)
#define FAST_IO std::ios::sync_with_stdio(false)
#define ll long long
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
const double Pi = acos(-1.0);
using namespace std;
template <class T>void tomax(T&a,T b){ a=max(a,b); }
template <class T>void tomin(T&a,T b){ a=min(a,b); }
const int N=5e5+5;
ll num[N];
struct Segt{
    #define lc (p<<1)
    #define rc (p<<1|1)
    #define MID (tree[p].l+tree[p].r)>>1;
    struct Seg{
        int l,r;
        ll _gcd;
        void init(int left,int right){
            l=left;
            r=right;
            _gcd=0;
        }
    }tree[N<<2];
    void pushdown(int p){ tree[p]._gcd=__gcd(tree[lc]._gcd,tree[rc]._gcd); }
    void build(int l,int r,int p){
        tree[p].init(l,r);
        if(l==r){
            tree[p]._gcd=num[l]-num[l-1];
            return ;
        }
        int mid=MID;
        build(l,mid,lc);
        build(mid+1,r,rc);
        pushdown(p);
    }
    void update(int pos,int p, ll val){
        if(tree[p].l==pos&&tree[p].r==pos){
            tree[p]._gcd+=val;
            return ;       
        }
        int mid=MID;
        if(pos<=mid) update(pos,lc,val);
        if(pos>mid) update(pos,rc,val);
        pushdown(p);
    }
    ll getans(int l,int r,int p){
        if(l>r) return 0;
        if(tree[p].l>=l&&tree[p].r<=r) return tree[p]._gcd;
        ll gcd=0;
        int mid=MID;
        if(l<=mid) gcd=__gcd(gcd,getans(l,r,lc));
        if(r>mid) gcd=__gcd(gcd,getans(l,r,rc));
        return gcd;
    }
}t;
struct BIT{
    int n;
    ll w[N];
    #define bit(x) (x&(-x))
    void update(int pos,ll val){
        for(int i=pos;i<=n;i+=bit(i)) w[i]+=val;
    }
    ll get(int pos){
        ll ans=0;
        for(int i=pos;i>0;i-=bit(i)) ans+=w[i];
        return ans;
    }
}s;
int main(){
    int n,m; Sca2(n,m);
    s.n=n;
    For(i,1,n){
        Scl(num[i]);   
    }
    t.build(1,n,1);
    while(m--){
        char cmd;int l,r;
        scanf(" %c%d%d",&cmd,&l,&r);
        if(cmd=='Q'){
            Prl(abs(__gcd(s.get(l)+num[l],t.getans(l+1,r,1))));
        }
        else if(cmd=='C'){
            ll val; Scl(val);
            if(r!=n){
                t.update(r+1,1,-val);
                s.update(r+1,-val);
            }
            t.update(l,1,val);
            s.update(l,val);
        }
    }
}