<h1>题目描述</h1>

题目链接
小Z经营一家加油店。小Z加油的方式非常奇怪。他有一排瓶子，每个瓶子有一个容量vi。每次别人来加油，他会让
别人选连续一段的瓶子。他可以用这些瓶子装汽油，但他只有三种操作：

1. 把一个瓶子完全加满；
2. 把一个瓶子完全倒空；
3. 把一个瓶子里的汽油倒进另一个瓶子，直到倒出瓶子空了或者倒进的瓶子满了。
   当然，为了回馈用户，小Z会时不时选择连续一段瓶子，给每个瓶子容积都增加x。

为了尽可能给更多的人加油，每次客户来加油他都想知道他能够倒腾出的汽油量最少是多少？
当然他不会一点汽油都不给客户。

<h1>解题报告</h1>

首先考虑只有询问怎么做。
一个显然的结论是：能表示出来的最小的数字一定是这些数字的gcd。
所以只有询问的话倍增处理一下gcd就可以了，时间复杂度 $O(nlog^2n)$
然后考虑加入了修改怎么做。
如果只有单点修改还是比较好做的，用线段树维护一下区间gcd，每次修改和查询都是 $O(log^2n)$ 的，总复杂度 $O(nlog^2n)$。
但是这里要求是区间修改，怎么办呢？
我们考虑将这个区间修改变成单点修改可以解决的问题，注意到 $\text{gcd}(a,b) = \text{gcd}(b,a-b)$,所以区间 $[l,r]$ 的 gcd 等价于将这个区间差分后的 gcd。
于是我们用线段树维护一下差分后的数组的区间 gcd 和区间和，支持单点修改和区间查询即可。
时间复杂度 $O(nlog^2n)$

<h1>代码</h1>

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 100000+5;

struct SegmentTree New(int ,int ,SegmentTree ,SegmentTree *);

int _gcd(int a,int b){
    return (!b) ? a : _gcd(b,a%b);
}

struct SegmentTree{
    int l,r,gcd,sum;
    SegmentTree lc,rc;
    
    static SegmentTree *build(int l,int r){
        int mid = (l + r) >> 1;
        return (l == r) ? New(l,r,NULL,NULL) : New(l,r,build(l,mid),build(mid+1,r));
    }

    void pushup(){
        gcd = _gcd(lc->gcd,rc->gcd);
        sum = lc->sum + rc->sum;
    }

    void update(int pos,int x){
        if(l == r){
            gcd += x;sum += x;
            return;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid) lc->update(pos,x);
        else rc->update(pos,x);
        pushup();
    }

    int querygcd(int L,int R){
        if(L > R) return 0;
        if(L == l && R == r) return gcd;
        int mid = (l + r) >> 1;
        if(R <= mid) return lc->querygcd(L,R);
        if(L > mid) return rc->querygcd(L,R);
        return _gcd(lc->querygcd(L,mid),rc->querygcd(mid+1,R));
    }

    int querysum(int L,int R){
        //if(L > R) return 0;
        if(L == l && R == r) return sum;
        int mid = (l + r) >> 1;
        if(R <= mid) return lc->querysum(L,R);
        if(L > mid) return rc->querysum(L,R);
        return lc->querysum(L,mid)+rc->querysum(mid+1,R);
    }
}pool[MAXN<<2],frog = pool,segt;

SegmentTree New(int l,int r,SegmentTree lc,SegmentTree *rc){
    SegmentTree *ret = ++frog;
    ret->l = l;ret->r = r;
    ret->lc = lc;ret->rc = rc;
    ret->gcd = 0;ret->sum = 0;
    return ret;
}

int N,M;
int a[MAXN],c[MAXN];

signed main(){
    scanf("%lld%lld",&N,&M);
    segt = SegmentTree::build(1,N);
    FOR(i,1,N){
        scanf("%lld",a+i);
        segt->update(i,a[i]-a[i-1]);
    }
    while(M--){
        int opt,l,r;scanf("%lld%lld%lld",&opt,&l,&r);
        if(opt == 1) printf("%ldn",std::labs(_gcd(segt->querysum(1,l),segt->querygcd(l+1,r))));
        else{
            int x;scanf("%lld",&x);
            segt->update(l,x);
            if(r < N) segt->update(r+1,-x);
        }
    }
    return 0;
}
/*
3 4
2 3 4
1 1 3
2 2 2 1
1 1 3
1 2 3   
*/