记录编号	582320	评测结果	AAAA
题目名称	区间最大公约数	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.998 s
提交时间	2023-09-09 15:26:36	内存使用	120.18 MiB

#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N = 1e6+10;
ll n,m;
char ch[10];
ll a[N],b[N],c[N];
ll gcd(ll x,ll y){
    x = abs(x),y = abs(y);
    if(x == 0)return y;
    if(y%x == 0)return x;
    return gcd(y,x%y); 
}
ll ask1(int x){
    ll ans = 0;
    for(;x;x -= x&-x)ans += c[x];
    return ans;
}
void add1(int x,ll ed){
    for(;x <= n;x += x&-x)c[x] += ed;
    return;
}
struct made{
    ll l,r;
    ll gc;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define gc(x) t[x].gc
}t[N<<2];
void build(int x,int l,int r){
    l(x) = l,r(x) = r;
    if(l == r){
        gc(x) = b[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    gc(x) = gcd(gc(x<<1),gc(x<<1|1));
}
void add(int x,int l,ll ed){
    if(l(x) == r(x)){
        gc(x) += ed;
        return;
    }
    int mid = (l(x) + r(x)) >> 1;
    if(l <= mid)add(x<<1,l,ed);
    else add(x<<1|1,l,ed);
    gc(x) = gcd(gc(x<<1),gc(x<<1|1));
}
ll ask(int x,int l,int r){
    if(l <= l(x) && r(x) <= r)return gc(x);
    int mid = (l(x) + r(x)) >> 1;
    if(r <= mid)return ask(x<<1,l,r);
    if(l > mid)return ask(x<<1|1,l,r);
    ll c = gcd(ask(x<<1,l,mid),ask(x<<1|1,mid+1,r));
    return c;
}
int main(){
    freopen("interval_gcd.in","r",stdin);
    freopen("interval_gcd.out","w",stdout);
    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);
    for(int i = 1;i <= m;i++){
        ll x,y,z;
        scanf("%s%lld%lld",ch,&x,&y);
        if(ch[0] == 'Q')printf("%lld\n",gcd(a[x]+ask1(x),ask(1,x+1,y)));
        else{
            scanf("%lld",&z);
            add(1,x,z);
            add1(x,z);
            if(y+1 <= n){
                add(1,y+1,-z);
                add1(y+1,-z);
            }
        }
    }
    
    return 0;
}