这道题难点就是在于区间加的维护。
考虑更相减损法,$gcd(a,b)=gcd(a,b-a)$,是可以推广到多个数的
因此维护一个差分数组就好了,区间加转化成$d[l],d[r+1]$的单点修改。
打个树状数组+线段树就好了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
using namespace std;
const int N=5e5+5;
template<class lb>
inline void qr(lb &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(ll x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
ll d[N<<2],b[N];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void build(int p,int l,int r)
{
if(l==r){d[p]=b[l];return ;}
int mid=l+r>>1;build(p<<1,l,mid),build(p<<1|1,mid+1,r);
d[p]=gcd(d[p<<1],d[p<<1|1]);
}
void change(int p,int l,int r,int x,ll val)
{
if(l==r){d[p]+=val;return ;}
int mid=l+r>>1;
if(x<=mid)change(p<<1,l,mid,x,val);
else change(p<<1|1,mid+1,r,x,val);
d[p]=gcd(d[p<<1],d[p<<1|1]);
}
ll query(int p,int l,int r,int ql,int qr)
{
if(ql<=l&&qr>=r)return d[p];
int mid=l+r>>1;ll val=0;
if(ql<=mid)val=gcd(val,query(p<<1,l,mid,ql,qr));
if(qr>mid)val=gcd(val,query(p<<1|1,mid+1,r,ql,qr));
return val;
}
ll c[N],a[N];int n,m;
inline void add(int x,ll val){for(;x<=n;x+=x&-x)c[x]+=val;}
inline ll ask(int x){ll ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
int main()
{
qr(n);qr(m);
for(int i=1;i<=n;i++)qr(a[i]);
for(int i=2;i<=n;i++)b[i]=a[i]-a[i-1];
build(1,1,n);
for(int i=1;i<=m;i++)
{
char op[3];scanf("%s",op);
if(op[0]=='C'){int l,r;ll val;qr(l),qr(r),qr(val);change(1,1,n,l,val);if(r+1<=n)change(1,1,n,r+1,-val);add(l,val),add(r+1,-val);}
else
{
int l,r;qr(l);qr(r);
ll ans=gcd(a[l]+ask(l),query(1,1,n,l+1,r));
qw(abs(ans));puts("");
}
}
return 0;
}
最后一次更新于2019-10-11
0 条评论