小阳的贝壳

题意：
有n个有颜色的贝壳，每一个的颜色值为col[i],小阳能进行以下三种操作：
1 l r x：给 [l,r]区间里所有贝壳的颜色值加上x。

2 l r：询问 [l,r]区间里所有相邻贝壳颜色值的差（取绝对值）的最大值（若l=r输出0）。

3 l r ：询问 [l,r]区间里所有贝壳颜色值的最大公约数。

思路：
先构造一个差分数组，根据差分数组构造线段树，维护区间值的和、区间值绝对值的最大值、区间值的最大公约数（gcd是具有区间可维护性的，即gcd(a,b,c,d) = gcd(gcd(a,b),gcd(c,d))）.

操作一：在线段树中更新（l-1)的位置加x,r的位置加（-x）。

操作二：在线段树中询问[l,r-1]区间的绝对值的最大值。

操作三：在线段树中询问[l,r-1]区间的绝对值的最大公约数，以及[1,l-1]区间的区间值的和。(gcd(a,b,c,d)=gcd(a,b-a,c-b,d-c),即[l,r]区间里所有贝壳颜色值的最大公约数为gcd(a[l],[l-r-1]区间的绝对值的最大公约数),a[l]=a[1]+[1,l-1]区间的区间值的和.)

代码：

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

typedef long long ll;

int n, m, a[100005], b[100005];

struct w
{
    int m, g, v;
}w[400005];


void build(int p,int l,int r)
{
    if(l==r)
    {
        w[p].v=b[l];
        w[p].g=abs(b[l]);
        w[p].m=abs(b[l]);
        return ;
    }
    else if(l>r)
    {
        return ;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    w[p].g=__gcd(w[p*2].g,w[p*2+1].g);
    w[p].m=max(w[p*2].m,w[p*2+1].m);
    w[p].v=w[p*2].v+w[p*2+1].v;
}

void change(int p,int l,int r,int x,int v)
{
    if(l==r&&l==x)
    {
        w[p].v+=v;
        w[p].m=abs(w[p].v);
        w[p].g=abs(w[p].v);
        return ;
    }
    int mid=(l+r)/2;
    if(mid>=x)
    {
        change(p*2,l,mid,x,v);
    }
    else
    {
        change(p*2+1,mid+1,r,x,v);
    }
    w[p].g=__gcd(w[p*2].g,w[p*2+1].g);
    w[p].m=max(w[p*2].m,w[p*2+1].m);
    w[p].v=w[p*2].v+w[p*2+1].v;
}

int ask(int p,int l,int r,int x,int y)
{
    if(l>r||x>y)
    {
        return 0;
    }
    if(x<=l&&r<=y)
    {
        return w[p].m;
    }
    int mid=(l+r)/2;
    if(x>mid)
    {
        return ask(p*2+1,mid+1,r,x,y);
    }
    if(y<=mid)
    {
        return ask(p*2,l,mid,x,y);
    }
    return max(ask(p*2,l,mid,x,mid),ask(p*2+1,mid+1,r,mid+1,y));
}

int ask1(int p,int l,int r,int x,int y)
{
    if(l>r||x>y)
    {
        return 0;
    }
    if(x<=l&&r<=y)
    {
        return w[p].v;
    }
    int mid=(l+r)/2;
    if(x>mid)
    {
        return ask1(p*2+1,mid+1,r,x,y);
    }
    if(y<=mid)
    {
        return ask1(p*2,l,mid,x,y);
    }
    return ask1(p*2,l,mid,x,mid)+ask1(p*2+1,mid+1,r,mid+1,y);
}

int ask2(int p,int l,int r,int x,int y)
{
    if(l>r||x>y)
    {
        return 0;
    }
    if(x<=l&&r<=y)
    {
        return w[p].g;
    }
    int mid=(l+r)/2;
    if(x>mid)
    {
        return ask2(p*2+1,mid+1,r,x,y);
    }
    if(y<=mid)
    {
        return ask2(p*2,l,mid,x,y);
    }
    return __gcd(ask2(p*2,l,mid,x,mid),ask2(p*2+1,mid+1,r,mid+1,y));
}


int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n-1;i++)
    {
        b[i]=a[i+1]-a[i];
    }
    build(1,1,n-1);
    while(m--)
    {
        int k;
        scanf("%d",&k);
        if(k==1)
        {
            int l, r, x;
            scanf("%d%d%d",&l,&r,&x);
            if(l==1)
            {
                a[1]+=x;
            }
            else
            {
                change(1,1,n-1,l-1,x);
            }
            if(r==n)
            {
                ;
            }
            else
            {
                change(1,1,n-1,r,-x);
            }
        }
        else if(k==2)
        {
            int l, r;
            scanf("%d%d",&l,&r);
            if(l==r)
            {
                printf("0\n");
            }
            else
            {
                printf("%d\n",ask(1,1,n-1,l,r-1));
            }
        }
        else
        {
            int l, r;
            scanf("%d%d",&l,&r);
            printf("%d\n",__gcd((a[1]+ask1(1,1,n-1,1,l-1)),ask2(1,1,n-1,l,r-1)));
        }
    }
    return 0;
}