小阳的贝壳题解

前言

在错了N次之后，改动了一个小地方，多了一个+1就过了这一题，太惨了。

思路

假设只有前两个操作，我们实际上只需要生成一个差分数组，维护一个单点修改以及区间查询最大值即可。

但是最难的是操作3，区间GCD。

小蒟蒻在这里卡了许久，冥思苦想还是没有想到办法，最后百度：差分数组与区间GCD

然后知道了这个柿子:

$gcd(a_1,a_2,a_3,...,a_n) = gcd(a_1,abs(a_2 - a_1),abs(a_3 - a_2),...,abs(a_n - a_n - 1))$

也就是:

$gcd(a_l,a_{l+1},a_{l+2},...,a_r) = gcd(a_l,abs(a_{l + 1} - a_l),abs(a_{l + 2} - a_{l + 1}),...,abs(a_{r} - a_{r - 1}))$

于是整个题目的基本做法已经出来了：

维护一个差分数组的绝对值最大值以及绝对值的gcd，然后对于每次操作1，就相当于是进行了一次单点修改,然后要维护区间信息，剩余的两个就是区间查询.gcd是具有区间可维护性的，也就是gcd(a,b,c,d) = gcd(gcd(a,b),gcd(c,d))

于是可以使用线段树。

我的做法是：

开两棵线段树，一棵维护差分数组，一棵维护原数组(操作三需要知道 $a_l$ 是多少)。

第一棵线段树存的是 $Max,gcd,l,r$

第二棵是： $data,laz,l,r$

对于操作一，在线段树一进行单点修改，线段树二中进行区间修改。
对于操作二,直接在线段树一中进行区间查询 $[l + 1 , r]$ 的最大值（因为是差分数组，所以维护的是 $a[i] - a[i - 1]$ ,因此查询的左端点要+1！就是这里导致我Wa了n次）
对于操作三，调用第二棵线段树求出 $a_l$ ,然后再调用线段树查询区间 $[l + 1,r]$ 差分绝对值数组的gcd，然后再对得到的这两个值进行gcd查询。

更优的做法是：

~~不难看出我是个shabi,居然开了两棵线段树~~

假定得到的差分数组为 $b[]$ , $b[i] = a[i] - a[i - 1]$

那么实际上 $a[i] = b[1] + b[2] + ... + b[i - 1] + a[1]$

开一棵线段树即可。维护区间GCD，区间差分数组最大值，区间和

这个做法好多了，好写又好调。

最后放上小蒟蒻丑丑的代码：

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 50;
int data[MAXN],n,Q;//data[]表示给定数组
int cha[MAXN];//差分数组

struct SegmentTree {
    int Max,l,r,G,v,laz,sum;
} T[MAXN * 4]; 

inline int read()
{
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

void build(int x,int l,int r)//建树的时候我的线段树一和线段树二是一起建的，并且用的同一个结构体
{
    T[x].l = l , T[x].r = r;
    if(l == r){T[x].Max = T[x].G = abs(cha[l]) ; T[x].v = cha[l] , T[x].sum = data[l]; return ; }
    int mid = (l + r) >> 1ll;
    build(x << 1 , l , mid);
    build(x << 1 | 1 , mid + 1 , r);
    T[x].Max = max(T[x << 1].Max , T[x << 1 | 1].Max);
    T[x].G = __gcd(T[x << 1].G, T[x << 1 | 1].G);
    return ;
}

//下面是第一棵线段树 ------ start -------

void change(int x,int pos,int k) //单点修改信息
{
    if(pos > n || pos < 0) return ;
    if(T[x].l == pos && T[x].r == pos){
        T[x].v += k; 
        T[x].Max = abs(T[x].v);
        T[x].G = abs(T[x].v);
        return ;
    }
    int mid = (T[x].l + T[x].r) >> 1;
    if(pos <= mid) change(x << 1 , pos , k);
    else change(x << 1 | 1 , pos, k);
    T[x].Max = max(T[x << 1].Max , T[x << 1 | 1].Max);
    T[x].G = __gcd(T[x << 1].G, T[x << 1 | 1].G);
    return ;
}

int GetMax(int x,int l,int r)//获得差分数组区间最大值
{
    int Max = -0x3f;
    if(T[x].l >= l && T[x].r <= r) return T[x].Max;
    int mid = (T[x].l + T[x].r) >> 1;
    if(l <= mid) Max = max(Max,GetMax(x << 1 , l ,r));
    if(r >  mid) Max = max(Max,GetMax(x << 1 | 1 , l ,r));
    return Max;
}

int GetGCD(int x,int l,int r)//获得区间gcd
{
    int G = 0;
    if(T[x].l >= l && T[x].r <= r) return T[x].G;
    int mid = (T[x].l + T[x].r) >> 1;
    if(l <= mid) G = __gcd(G,GetGCD(x << 1 , l , r)); 
    if(r > mid) G = __gcd(G,GetGCD(x << 1 | 1 , l , r));
    return G;
}

//线段树1 ------ end ------

//下面是第二棵线段树 ------- start --------

void ad(int x,int k)
{
    T[x].laz += k;
    T[x].sum = T[x].sum +  k;
    return ;
}

void pushdown(int x)//懒标记下传
{
    if(T[x].laz == 0ll) return ;
    ad(x << 1 , T[x].laz);
    ad(x << 1 | 1 , T[x].laz);
    T[x].laz = 0;
    return ;
}

int Get(int x,int pos)//获得单点值
{
    if(T[x].l == T[x].r && T[x].l == pos) return T[x].sum;
    pushdown(x);
    int mid = (T[x].l + T[x].r) >> 1;
    if(pos <= mid) return Get(x << 1 , pos);
    else return Get(x << 1 | 1 , pos);
}

void changesum(int x,int l,int r,int k)
{
    if(T[x].l >= l && T[x].r <= r) {ad(x,k) ; return ;};
    pushdown(x);
    int mid = (T[x].l + T[x].r) >> 1;
    if(l <= mid) changesum(x << 1 , l , r , k);
    if(r > mid) changesum(x << 1 | 1 , l , r , k);
    return ;
}
// 第二棵线段树 ------- end --------

signed main()
{
    n = read() , Q = read();
    for(int i = 1 ; i <= n ; i ++) 
        data[i] = read(),cha[i] = data[i] - data[i - 1];
    cha[1] = 0;//实际上我的做法用不到差分数组第一个数，赋值成0
    build(1 , 1 , n);
    while(Q --)
    {
        int op = read(),l = read() , r = read() , x;
        if(op == 1) x = read();
        if(op == 1) 
        {
            change(1,l, x);
            change(1,r + 1 , -x);//单点修改
            changesum(1,l,r,x);//区间修改
            continue;
        }
        if(op == 2)
        {
            if(l == r) {cout << 0 << endl; continue;}
            cout << GetMax(1,l + 1,r) << endl;//!!!这里注意一定要+1，血淋淋的教训！
            //因为是差分数组，所以维护的是a[i] - a[i - 1]，题目求的是[l,r],如果不加+1，就求成[l - 1 , r] 了。
        }
        else 
        {
            if(l == r) {cout << Get(1,l) << endl; continue;}//特判一下
            cout << __gcd(Get(1,l),GetGCD(1,l + 1 , r)) << endl;
        }
    }
    return 0;
}

小阳的贝壳 题解

前言

思路

我的做法是：

更优的做法是：

Code

小阳的贝壳题解