易错点:
- 线段树查询时直接保留查询范围即可.
- 线段树递归结束后,返回gcd结果时应取绝对值.
- 本题线段树初始化时需要使用差分数组(更相减损术);同样地,在进行区间修改时[l~r]的修改会影响到线段树内[l~r+1]的值.
- 修改时应特判r>n的情况.
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int MAXN=6e5;
struct Node{
int l,r;
ll val;
}tr[MAXN*4];
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
ll b[MAXN];
void build(int p,int l,int r){
tr[p].l=l,tr[p].r=r;
if(l==r){
tr[p].val=b[l];
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build((p<<1)|1,mid+1,r);
tr[p].val=gcd(tr[p<<1].val,tr[(p<<1)|1].val);
}
ll query(int p,int l,int r){
if(tr[p].l>=l&&tr[p].r<=r){
return abs(tr[p].val);
}
int mid=(tr[p].l+tr[p].r)>>1;
ll ans=0;
if(l<=mid)ans=gcd(ans,query(p<<1,l,r));
if(r>mid)ans=gcd(ans,query((p<<1)|1,l,r));
return abs(ans);
}
void change(int p,int x,ll val){
if(tr[p].l==tr[p].r){
tr[p].val+=val;
return;
}
int mid=(tr[p].l+tr[p].r)>>1;
if(x<=mid)change(p<<1,x,val);
else change((p<<1)|1,x,val);
tr[p].val=gcd(tr[p<<1].val,tr[(p<<1)|1].val);
}
int lowbit(int x){
return x&-x;
}
int n;
ll c[MAXN];
void add(int x,ll val){
while(x<=n){
c[x]+=val;
x+=lowbit(x);
}
}
ll ask(int x){
ll ans=0;
while(x){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
ll a[MAXN];
int root=1;
int main(){
int m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
b[i]=a[i]-a[i-1];
}
build(root,1,n);
char tmp[2];
for(int i=1;i<=m;i++){
int l,r;
scanf("%s%d%d",tmp,&l,&r);
if(tmp[0]=='C'){
ll delta;
scanf("%lld",&delta);
change(root,l,delta);
if(r<n)change(root,r+1,-delta);
add(l,delta),add(r+1,-delta);
}else{
ll alValue=a[l]+ask(l);
ll val=l<r?query(root,l+1,r):0;
printf("%lld\n",gcd(alValue,val));
}
}
return 0;
}
等等,好像过不了样例?
谢谢指正