NC26255 小阳的贝壳

题目描述

小阳手中一共有 $n$ 个贝壳，每个贝壳都有颜色，且初始第 $i$ 个贝壳的颜色为 $col_i$ 。现在小阳有 $3$ 种操作。 $\text{1 l r x}$ ：给 $[l，r]$ 区间里所有贝壳的颜色值加上 $x$ 。 $\text{2 l r}$ ：询问 $[l，r]$ 区间里所有相邻贝壳颜色值的差（取绝对值）的最大值（若 $l=r$ 输出 $0$ ）。 $\text{3 l r}$ ：询问 $[l，r]$ 区间里所有贝壳颜色值的最大公约数。

输入描述

第一行输入两个正整数 $n,m$ ，分别表示贝壳个数和操作个数。
第二行输入 $n$ 个数 $col_i$ ，表示每个贝壳的初始颜色。
第三到第 $m + 2$ 行，每行第一个数为 $opt$ ，表示操作编号。接下来的输入的变量与操作编号对应。

输出描述

共 $m$ 行，对于每个询问（操作 $2$ 和操作 $3$ ）输出对应的结果。

示例1

输入
5 6
2 2 3 3 3
1 2 3 3
2 2 4
3 3 5
1 1 4 2
3 2 3
2 3 5
输出
3
3
1
3

备注

$1 \leq n,m \leq 10^5,1 \leq col_i,x \leq 10^3,1 \leq opt \leq 3,1 \leq l \leq r \leq n$ 。

分析

区间修改查询的操作，第一反应是区间修改和区间查询的线段树，但是一时无从下手。
对于数组的区间修改，另一个常用的策略是使用差分数组，设数组 $col_i$ 的差分数组为 $d_i$ 。
进行操作 $1$ 区间加时，相当于对差分数组 $d_l$ 和 $d_{r+1}$ 的单点修改。因此不妨用一颗线段树维护 $d_i$ ，对其进行单点修改。
进行操作 $2$ 时，求的是区间 $[l,r]$ 内 $|col_i-col_{i-1}|(l+1\le i\le r)$ 的最大值，也就是求区间 $[l+1,r]$ 内 $|d_i|$ 的最大值。因此不妨用一颗线段树维护区间内 $|d_i|$ 的最大值。
进行操作 $3$ 时，显然有 $\gcd(col_l,col_{l+1},\cdots,col_r)$ $=$ $\gcd(col_l,|col_{l+1}-col_l|,\cdots,|col_r-col_{r-1}|)$ $=$ $\gcd(col_i,|d_{l+1}|,\cdots,|d_r|)$ $=$ $\gcd(\sum\limits_{i=1}^l d_i,|d_{l+1}|,\cdots,|d_r|)$ 。因此不妨用一颗线段树维护区间内 $|d_i|$ 的最小公倍数和 $d_i$ 的区间和。
综上所述，线段树上节点包含的信息有，区间内 $d_i$ 的和、区间内 $|d_i|$ 的最大公约数、区间内 $|d_i|$ 的最大值。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 100006
using namespace std;
int col[N];
int d[N];//差分
int n,m;
struct SegmentTree
{
    int l,r;
    int maximum;//区间内|d[i]|最大值
    int gcd;//区间内|d[i]|最大公约数
    int sum;//区间内d[i]的和
}tree[N<<2];
void pushup(int id)//自底向上递推
{
    int ls=id<<1;
    int rs=id<<1|1;
    tree[id].gcd=__gcd(tree[ls].gcd,tree[rs].gcd);
    tree[id].maximum=max(tree[ls].maximum,tree[rs].maximum);
    tree[id].sum=tree[ls].sum+tree[rs].sum;
}
void build(int id,int l,int r)//建树
{
    tree[id].l=l;
    tree[id].r=r;
    if(l==r)
    {
        tree[id].gcd=tree[id].maximum=abs(d[l]);
        tree[id].sum=d[l];
        return;
    }
    int mid=l+r>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    pushup(id);
}
int query_gcd(int id,int l,int r)//查询区间gcd
{
    if(l<=tree[id].l&&tree[id].r<=r) return tree[id].gcd;
    int mid=tree[id].l+tree[id].r>>1;
    int res=0;
    if(l<=mid) res=__gcd(res,query_gcd(id<<1,l,r));
    if(r>=mid+1) res=__gcd(res,query_gcd(id<<1|1,l,r));
    return res;
}
int query_sum(int id,int l,int r)//查询区间和
{
    if(l<=tree[id].l&&tree[id].r<=r) return tree[id].sum;
    int mid=tree[id].l+tree[id].r>>1;
    int res=0;
    if(l<=mid) res+=query_sum(id<<1,l,r);
    if(r>=mid+1) res+=query_sum(id<<1|1,l,r);
    return res;
}
int query_max(int id,int l,int r)//查询区间最大值
{
    if(l<=tree[id].l&&tree[id].r<=r) return tree[id].maximum;
    int mid=tree[id].l+tree[id].r>>1;
    int res=0;
    if(l<=mid) res=max(res,query_max(id<<1,l,r));
    if(r>=mid+1) res=max(res,query_max(id<<1|1,l,r));
    return res;
}
void update(int id,int pos,int x)//单点更新
{
    if(tree[id].l==pos&&tree[id].r==pos)
    {
        tree[id].sum+=x;
        tree[id].maximum=abs(tree[id].sum);
        tree[id].gcd=abs(tree[id].sum);
        return;
    }
    int mid=tree[id].l+tree[id].r>>1;
    if(pos<=mid) update(id<<1,pos,x);
    else update(id<<1|1,pos,x);
    pushup(id);
}
int main()
{
    cin>>n>>m;
    int i;
    for(i=1;i<=n;i++) scanf("%d",col+i);
    for(i=1;i<=n;i++) d[i]=col[i]-col[i-1];
    build(1,1,n);
    while(m--)
    {
        int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==2) l==r?puts("0"):printf("%d\n",query_max(1,l+1,r));
        else if(opt==3) printf("%d\n",__gcd(query_sum(1,1,l),query_gcd(1,l+1,r)));
        else
        {
            int x;
            scanf("%lld",&x);
            //对差分数组进行单点更新
            update(1,l,x);
            if(r<n) update(1,r+1,-x);
        }
    }
    return 0;
}