每日一题: 小阳的贝壳(线段树维护差分数组)

传送门

$T1$

假设只有操作一和操作三

操作一普通线段树可以完成,操作三普通线段树也能完成

做法是维护一个 $cd[rt]$ 数组表示 $rt$ 节点表示区间的 $gcd$

由于 $gcd$ 具有传递性,所以很容易维护。

$T_2$

假如只有操作一和操作三

操作一普通线段树可以轻松完成,操作二的话....势必要维护一个差分数组

也就是令 $b[i]=a[i]-a[i-1]$

在线段树上维护这个 $b$ 数组的关系

比如在 $[l,r]$ 区间内加 $x$ ,只需要在 $l$ 加 $x$ 以及在 $r+1$ 位置减 $x$

那么求最大的绝对值的 $b$ 数组,只需要维护一个 $v$ 表示 $b$ 的绝对值即可

$T_3$

有了 $T_1$ 和 $T_2$ ,思路就出来了

建立两颗线段树,一颗维护原数组 $a$ ,一颗维护差分数组 $b$

第一棵树解决区间 $gcd$ 问题,第二棵树解决区间最大差值问题

~~但是我没有写代码因为还有T_4~~

$T_4$

其实只需要维护差分数组的线段树就能解决区间 $gcd$ 问题

因为有定理 $gcd(a,b,c)=gcd(a,b-a,c-b)$

所以 $[l,r]$ 的 $gcd$ 就是原数组的 $a[l]$ 和差分数组 $[l+1,r]$ 区间的 $gcd$

那么就好办了。

#include <bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,r
const int maxn = 1e5+10;
int a[maxn],b[maxn],n,m;
int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }
int sum[maxn<<2],cd[maxn<<2],mx[maxn<<2],laz[maxn<<2];
void pushup(int rt,int l,int r)
{
    sum[rt] = sum[ls]+sum[rs];
    cd[rt] = gcd( cd[ls],cd[rs] );//gcd
    mx[rt] = max( mx[ls],mx[rs] );//最大的颜色差绝对值 
}
void build(int rt,int l,int r)//维护区间gcd,相邻绝对值最大,区间和 
{
    if( l==r ){ sum[rt]=b[l],cd[rt]=mx[rt]=abs(b[l]); return; }
    build(lson); build(rson);
    pushup(rt,l,r);
}
void update(int rt,int l,int r,int index,int val)
{
    if( l>index||r<index )    return;
    if( l==r ){ sum[rt]+=val,cd[rt]=mx[rt]=abs(sum[rt]); return; }
    update(lson,index,val); update(rson,index,val);
    pushup(rt,l,r);
}
int asksum(int rt,int l,int r,int L,int R)//群问区间和 
{
    if( l>R||r<L )    return 0;
    if( l>=L&&r<=R )    return sum[rt];
    return asksum(lson,L,R)+asksum(rson,L,R);
}
int askgcd(int rt,int l,int r,int L,int R)
{
    if( l>R||r<L )    return 0;
    if( l>=L&&r<=R )    return cd[rt];
    return gcd( askgcd(lson,L,R),askgcd(rson,L,R) );
}
int askmax(int rt,int l,int r,int L,int R)
{
    if( l>R||r<L )    return 0;
    if( l>=L&&r<=R )    return mx[rt];
    return max( askmax(lson,L,R),askmax(rson,L,R) );
}
int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)    scanf("%d",&a[i] );
    for(int i=1;i<=n;i++)    b[i] = a[i]-a[i-1];
    build(1,1,n);
    while( m-- )
    {
        int type,l,r,x; scanf("%d%d%d",&type,&l,&r);
        if( type==1 )
        {
            scanf("%d",&x);
            update(1,1,n,l,x); update(1,1,n,r+1,-x); 
        }
        else if( type==2 )
        {
            if( l==r )    printf("0\n");
            else    printf("%d\n",askmax(1,1,n,l+1,r) );
        }
        else
        {
            if( l==r )    printf("%d\n",asksum(1,1,n,1,l) );
            else    printf("%d\n",gcd( askgcd(1,1,n,l+1,r),asksum(1,1,n,1,l) ) );
        }
    }
}