C++(clang++11) 解法, 执行用时: 182ms, 内存消耗: 4128K, 提交时间: 2021-03-29 10:57:08

#include<iostream>
#include<algorithm>
using namespace std;
enum{maxn=400010};
int tree[maxn],arr[maxn];
int n;
void build(int l=1,int r=n,int p=1){
    if(l>r)return;
    if(l==r) {
        tree[p]=arr[l];
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,2*p);
    build(mid+1,r,2*p+1);
    tree[p]=__gcd(tree[2*p],tree[2*p+1]);
}
void addpoint(int pos,int k,int l=1,int r=n,int p=1){
    if(l>r)return ;
    if(l==r){
        tree[p]+=k;
        tree[p]=max(tree[p],0);
        return ;
    }
    int mid=(l+r)/2;
    if(pos>mid)addpoint(pos,k,mid+1,r,2*p+1);
    else addpoint(pos,k,l,mid,2*p);
    tree[p]=__gcd(tree[2*p],tree[2*p+1]);
}
int find(int fl,int fr,int l=1,int r=n,int p=1){
    if(l>r) return 0;
    if(fl<=l&&fr>=r) return tree[p];
    int mid=(l+r)/2;
    int a=0,b=0;
    if(fl<=mid) a=find(fl,fr,l,mid,2*p);
    if(fr>mid) b=find(fl,fr,mid+1,r,2*p+1);
    return __gcd(a,b);
}
int m;
char op[20];
int a,b;
int main(){
    //freopen("data.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>arr[i];
    build();
    for(int i=0;i<m;++i){
        cin>>op>>a>>b;
        switch(op[0]){
        case '+':
            addpoint(a,b);break;
        case '-':addpoint(a,-b);break;
        case 'Q':
            if(a>b) swap(a,b);
            cout<<find(a,b)<<endl;
        }
    }
}