原题链接
更好的阅读体验

题目描述

给定一个长度为$N$的数列$A$，以及$M$条指令，每条指令可能是以下两种之一：

1、“C l r d”，表示把 $A[l],A[l+1],…,A[r]$ 都加上 $d$。

2、“Q l r”，表示询问 $A[l],A[l+1],…,A[r]$ 的最大公约数(GCD)。

对于每个询问，输出一个整数表示答案。

输入格式
第一行两个整数$N$,$M$。

第二行$N$个整数$A[i]$。

接下来$M$行表示$M$条指令，每条指令的格式如题目描述所示。

输出格式
对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围
$N≤500000,M≤100000$

样例

输入样例：
5 5
1 3 5 7 9
Q 1 5
C 1 5 1
Q 1 5
C 3 3 6
Q 2 4
输出样例：
1
2
4

线段树

首先分析复杂度和题目隐含的区间可加性,我们可以确定这道题目是线段树,然后接着分析题意,这道题目大致是两个操作,区间修改,单点查询,同时我们还要维护区间最大公约数

其实这道题目,我们线段树并不需要区间修改,只需要单点修改即可,至于为什么可以不要,因为我们可以利用代码精简,常数较小的树状数组配合差分来强势维护.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
const long long N=501000;
struct line_tree
{
    long long l,r,dat;
    #define l(x) (x)<<1
    #define r(x) ((x)<<1)+1
} t[N<<2];
long long a[N],c[N],b[N],i,j,n,m;
long long gcd(long long a,long long b)
{
    return b?gcd(b,a%b):a;
}
long long sum(long long x)
{
    long long ans=0;
    for(;x;x-=lowbit(x))
        ans+=c[x];
    return ans;
}
void add(long long x,long long y)
{
    for(;x<=n;x+=lowbit(x))
        c[x]+=y;
}
void build(long long p,long long l,long long r)
{
    t[p].l=l;
    t[p].r=r;
    if (l==r)
    {
        t[p].dat=b[l];
        return ;
    }
    long long mid=(l+r)>>1;
    build(l(p),l,mid);
    build(r(p),mid+1,r);
    t[p].dat=gcd(t[l(p)].dat,t[r(p)].dat);
}
void change(long long p,long long x,long long v)
{
    if (t[p].l==t[p].r)
    {
        t[p].dat+=v;
        return ;
    }
    long long mid=(t[p].l+t[p].r)>>1;
    if (x<=mid)
        change(l(p),x,v);
    else
        change(r(p),x,v);
    t[p].dat=gcd(t[l(p)].dat,t[r(p)].dat);
}
long long ask(long long p,long long l,long long r)
{
    if (l<=t[p].l && r>=t[p].r)
        return t[p].dat;
    long long mid=(t[p].l+t[p].r)>>1;
    long long val=0;
    if (l<=mid)
        val=gcd(val,ask(l(p),l,r));
    if (r>mid)
        val=gcd(val,ask(r(p),l,r));
    return abs(val);
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        b[i]=a[i]-a[i-1];
    }
    build(1,1,n);
    while(m--)
    {
        char str[2]; 
        scanf("%s", str);
        long long l,r,x;
        scanf("%lld%lld",&l,&r);
        if (str[0]=='C')
        {
            scanf("%lld\n",&x);
            change(1,l,x);
            if (r<n)
                change(1,r+1,-x);
            add(l,x);
            add(r+1,-x);
        }
        else
        {
            scanf("\n");
            long long ans=a[l]+sum(l);
            long long ans_2=l<r ? ask(1,l+1,r):0;
            printf("%lld\n",gcd(ans,ans_2));
        }
    }
    return 0;
}