범위의 최대공약수 쿼리 최적화..

#include <iostream>
using namespace std;
typedef long long l;
l off,tree[300000],lazy[300000],n,input[100000],Q;
l gcd(l a,l b){
  if(!b)return a;
  return gcd(b,a%b);
}
void lazy_update(l node,l s,l e)
{
  if(lazy[node]>0){
      if(s==e){
        tree[node]+=lazy[node];
      }
      if(s!=e){
        lazy[node*2]+=lazy[node];
        lazy[node*2+1]+=lazy[node];
      }
    lazy[node]=0;
  }
}
void update(l node,l s,l e,l left,l right,l value){
  lazy_update(node,s,e);
  if(right<s||left>e)return;
  if(left<=s&&e<=right){
    if(s==e){
      tree[node]+=value;
    }
    if(s!=e){
      lazy[node*2]+=value;
      lazy[node*2+1]+=value;
    }
    return;
  }
  l mid=(s+e)/2;
  update(node*2,s,mid,left,right,value);
  update(node*2+1,mid+1,e,left,right,value);
  if(tree[node*2]==0)tree[node]=tree[node*2+1];
  else if(tree[node*2+1]==0)tree[node]=tree[node*2];
  else tree[node]=gcd(tree[node*2],tree[node*2+1]);
}
l query(l node,l s,l e,l left,l right){
  lazy_update(node,s,e);
  if(right<s||left>e)return 0;
  if(left<=s&&e<=right&&s==e)return tree[node];
  l mid=(s+e)/2,lv=query(node*2,s,mid,left,right),rv=query(node*2+1,mid+1,e,left,right);
  //if(lv==0)return rv;
  //if(rv==0)return lv;
  return gcd(lv,rv);
}
void init(){
  off=1;
  for(;off<n;)off*=2;
  for(l i=off;i<off+n;i++)tree[i]=input[i-off];
  for(l i=off+n;i<off*2;i++)tree[i]=0;
  for(l i=off-1;i>=1;i--){
    if(tree[i*2]==0)tree[i]=tree[i*2+1];
    else if(tree[i*2+1]==0)tree[i]=tree[i*2];
    else tree[i]=gcd(tree[i*2],tree[i*2+1]);
  }
}
void print(){
  puts("\n***************");
  for(int i=1;i<off*2;i++)cout<<tree[i]<<' ';
  puts("\n***************");
}
int main(){
  cin>>n;
  for(l i=0;i<n;i++)cin>>input[i];
  init();
  cin>>Q;
  for(l i=0;i<Q;i++){
    l T,A,B;
    cin>>T>>A>>B;
    if(T==0){
      printf("%lld\n",query(1,1,n,A,B));
    }
    else{
      update(1,1,n,A,B,T);
      //print();
    }
  }
}