第一个线段树维护差分,第二个线段树维护A数组的值 WA On line 1679 column 1, read 2, expected 6. 求大佬看看哪里错了
#include<bits/stdc++.h>
#define R register
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int MAXN=500005;
ll n,m,a[MAXN],b[MAXN];
ll x,y,z;
char t;
struct node{
int l,r;
ll w;
}tree[MAXN*4];
struct node2{
int l,r;
ll w,d;
}tree2[MAXN*4];
ll ggcd(ll t1,ll t2){
if(t2==0)return t1;
return ggcd(t2,t1%t2);
}
inline ll gcd(ll t1,ll t2){
if(t1<0)t1=-t1;
if(t2<0)t2=-t2;
return ggcd(t1,t2);
}
void build(int x,int l,int r){
tree[x].l=l,tree[x].r=r;
if(l==r){
tree[x].w=b[l];
return ;
}
int mid=(l+r)>>1;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
tree[x].w=gcd(tree[x*2].w,tree[x*2+1].w);
}
void build2(int x,int l,int r){
tree2[x].l=l,tree2[x].r=r;
if(l==r){
tree2[x].w=a[l];
return ;
}
int mid=(l+r)>>1;
build2(x*2,l,mid);
build2(x*2+1,mid+1,r);
tree2[x].w=tree2[x*2].w+tree2[x*2+1].w;
}
void down(int x){
tree2[x*2].d+=tree2[x].d;
tree2[x*2+1].d+=tree2[x].d;
tree2[x*2].w+=tree2[x].d*(tree2[x*2].r-tree2[x*2].l+1);
tree2[x*2+1].w+=tree2[x].d*(tree2[x*2+1].r-tree2[x*2+1].l+1);
tree2[x].d=0;
}
void add(int x,int l,ll t){
//cout<<tree[x].l<<" "<<tree[x].r<<" "<<tree[x].w<<"\n";
if(tree[x].l==0)return ;
if(tree[x].l==l&&tree[x].r==l)tree[x].w+=t;
int mid=(tree[x].l+tree[x].r)>>1;
if(l<=mid)return add(x*2,l,t);
else add(x*2+1,l,t);
tree[x].w=gcd(tree[x*2].w,tree[x*2+1].w);
}
void add2(int x,int l,int r,ll t){
//cout<<tree2[x].l<<" "<<tree2[x].r<<" "<<tree2[x].w<<"\n";
if(tree2[x].l>=l&&tree2[x].r<=r){
tree2[x].w+=t*(tree2[x].r-tree2[x].l+1);
tree2[x].d+=t;
return ;
}
if(tree2[x].d)down(x);
int mid=(tree2[x].l+tree2[x].r)>>1;
if(l<=mid)add2(x*2,l,r,t);
if(r>mid)add2(x*2+1,l,r,t);
tree2[x].w=tree2[x*2].w+tree2[x*2+1].w;
}
ll check(int x,int l,int r){
//cout<<tree[x].l<<" "<<tree[x].r<<" "<<tree[x].w<<"\n";
if(tree[x].l>=l&&tree[x].r<=r)return tree[x].w;
int mid=(tree[x].l+tree[x].r)>>1;
ll tmp=0;
if(l<=mid)tmp=check(x*2,l,r);
if(r>mid)tmp=gcd(tmp,check(x*2+1,l,r));
return tmp;
}
ll check2(int x,int l){
if(tree2[x].l==l&&tree[x].r==l)return tree2[x].w;
if(tree2[x].d)down(x);
int mid=(tree2[x].l+tree2[x].r)>>1;
if(l<=mid)return check2(x*2,l);
return check2(x*2+1,l);
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i]-a[i-1];
}
build(1,1,n);
build2(1,1,n);
//for(int i=1;i<=2*n;i++)cout<<tree[i].l<<" "<<tree[i].r<<" "<<tree[i].w<<"\n";
for(int i=1;i<=m;i++){
cin>>t;
if(t=='C'){
cin>>x>>y>>z;
add2(1,x,y,z);
add(1,x,z);
if(y!=n)add(1,y+1,-z);
}
else{
cin>>x>>y;
//cout<<"*"<<check2(1,x)<<" "<<check(1,x+1,y)<<"\n";
if(x==y)cout<<abs(check2(1,x))<<"\n";
else cout<<gcd(check2(1,x),check(1,x+1,y))<<"\n";
}
}
return 0;
}