更好的阅读体验

简述概念和应用

  所谓的差分，其实就是后一项与前一项的差，对于第一项而言， 。设数组 ，那么差分数组 ，即 ,那么，
NC26255 小阳的贝壳
  这题要求最大公因数和差分最值，最值上一题已经求过了，这最大公因数怎么维护出来呢？而且修改是区间修改的，这貌似也增加了维护最大公因数的难度。我们分开思考，如果只有 和 两种操作，区间加和差分是很好维护的，只需要在区间起始位置和终止位置加 处加上对应值即可（例如我们要原数组 区间加上 ,首先是要修改差分数组上的 ， 然后还要修改 ,这也是很好理解的，毕竟 区间比其他区间突出了一块，整体提高了 ，而其他的区间的差分关系并没有被改变）。
  我们接着思考最大公因数的求法，无非就是辗转相除法和更相减损术，诶，这更相减损术有点差分的意味了。根据更相减损术，有：
  我们想办法让他和差分联系起来。设原数组为 ,差分数组为 ，则有：
  拓展到多个整数的情况,对于区间 ，有：
  这样，我们通过维护差分数组 的区间和，区间绝对值最大值，区间最大公因数三个信息就可以做出这道题了。有思路的可以开始做了，代码并不难，只是注意什么值不取绝对值，什么值取绝对值。
  我的代码里有一个求 函数（百度的），如果是自己写记得要特判可能会除0的情况。还有一个办法是调用 库里的 的函数。

:

#include<bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
#define speedUp_cin_cout ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define mid (l+r)/2
#define ls now<<1
#define rs now<<1|1
const int maxn = 1e5+5;
inline int Gcd(int a,int b){
    if(a == 0) return b;
    if(b == 0) return a;
    while(b^=a^=b^=a%=b);
    return a;
}
int a[maxn],n,m,cha[maxn]; //a为原数组，cha为差分数组
//线段树节点
struct node{
    int sum,gcd,gap;//区间和，最大公因数，最大差的绝对值
}t[maxn<<2];

void pushup(int now){
    t[now].sum = t[ls].sum + t[rs].sum;      //直接加
    t[now].gcd = Gcd(t[ls].gcd,t[rs].gcd);      //两边取最大公约数
    t[now].gap = max(t[ls].gap,t[rs].gap);     //两边取最大差
}

void build(int now,int l,int r){
    if(l == r) {
        t[now].sum = cha[l];
        t[now].gcd = abs(cha[l]);     //取绝对值
        t[now].gap = abs(cha[l]);     //取绝对值
        return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(now);
}

void update(int now,int l,int r,int pos,int value){
    if(l == r) {
        t[now].sum = cha[l];
        t[now].gcd = abs(cha[l]);
        t[now].gap = abs(cha[l]);
        return;
    }
    if(pos <= mid) update(ls,l,mid,pos,value);
    else update(rs,mid+1,r,pos,value);
    pushup(now);
}

int queryGap(int now,int l,int r,int x,int y){
    if(x <= l && r <= y) return t[now].gap;
    int ans = 0;
    if(x <= mid) ans = max(ans,queryGap(ls,l,mid,x,y));
    if(y > mid) ans = max(ans,queryGap(rs,mid+1,r,x,y));
    return ans;
}

int querySum(int now,int l,int r,int x,int y){
    if(x <= l && r <= y) return t[now].sum;
    int ans = 0;
    if(x <= mid) ans += querySum(ls,l,mid,x,y);
    if(y > mid) ans += querySum(rs,mid+1,r,x,y);
    return ans;
}

int queryGcd(int now,int l,int r,int x,int y){
    if(x <= l && r <= y) return t[now].gcd;
    int ans = 0;
    if(x <= mid) ans = Gcd(ans,queryGcd(ls,l,mid,x,y));
    if(y > mid) ans = Gcd(ans,queryGcd(rs,mid+1,r,x,y));
    return ans;
}

int main(){
    speedUp_cin_cout
    cin>>n>>m;
    For(i,1,n) cin>>a[i],cha[i] = a[i] - a[i-1];
    build(1,1,n);
    int op,x,y,v;
    For(i,1,m){
        cin>>op>>x>>y;
        if(op == 1) {
            cin>>v;
            cha[x] += v;   //注意要修改一下查分数组，和我写法有关
            update(1,1,n,x,v);
            if(y < n) {        //如果不是最后一个还要修改一个单点
                cha[y+1] -= v;
                update(1,1,n,y+1,-v);
            }
        }else if(op == 2) cout<<queryGap(1,1,n,x+1,y)<<endl;  //操作2
        else cout<<Gcd(querySum(1,1,n,1,x),queryGcd(1,1,n,x+1,y))<<endl;  //操作3
    }
    return 0;
}

  希望对你理解有所帮助，如果有不清楚的的地方欢迎和我讨论o(*^▽^*)┛。