https://ac.nowcoder.com/acm/contest/1033/B
区间加,求 区间 gcd [L,R]
gcd (a[x],a[x+1],.....a[y] ) = gcd (a[x], a[x+1]-a[x], a[x+2]-a[x+1] ,..... a[y]-a[y-1] )
线段树维护差分数组的gcd,而区间加变为2个单点改
a[x] 的话要维护下差分数组的前缀和,和原来的a[x] 加起来
#include <iostream> #include <map> #include <cstring> #include <algorithm> using namespace std ; const int N =5e5+10; #define int long long #define k1 k<<1 #define k2 k<<1|1 struct TREE{ int l,r,g ; }tr[N<<2]; int n,a[N],df[N],c[N*2]; int lowbit(int x){ return x&-x; } int q(int x){ int res=0 ; for(;x;x-=lowbit(x)) res+=c[x]; return res; } void add(int x,int v){ for(;x<=n;x+=lowbit(x)) c[x]+=v; } int qry(int k,int x,int y){ int l=tr[k].l, r=tr[k].r; if(x<=l&&y>=r){ return abs(tr[k].g) ; } int md=(l+r)>>1; int t= 0; if(x<=md) t=__gcd(qry(k1,x,y),t); if(y>md) t=__gcd(qry(k2,x,y),t); return abs(t); } void build(int k,int l,int r){ tr[k].l=l,tr[k].r=r,tr[k].g= 0 ; if(l==r){ tr[k].g = df[l]; return ; } int md=(tr[k].l+tr[k].r)>>1; build(k1,l,md),build(k2,md+1,r); tr[k].g= __gcd(tr[k1].g,tr[k2].g) ; } void cg(int k,int x,int v){ int l=tr[k].l, r=tr[k].r; if(x==l&&l==r){ tr[k].g+=v; return ; } int md=(l+r)>>1; if(x<=md) cg(k1,x,v); else cg(k2,x,v); tr[k].g= __gcd(tr[k1].g,tr[k2].g) ; } // q(x,y) signed main(){ int i,x,y,z,tes; cin>>n>>tes ; for(i=1;i<=n;i++) cin>>a[i],df[i]=a[i]-a[i-1]; build(1,1,n) ; while(tes--){ char op ; cin>>op>>x>>y; if(op=='C'){ cin>>z; cg(1,x,z); if(y+1<=n) cg(1,y+1,-z); add(x,z),add(y+1,-z); } else{ int t1= a[x]+q(x), t2= qry(1,x+1,y) ; cout<<__gcd(t1,t2)<<'\n'; } } }
标签:md,GCD,int,interval,tr,build,include,gcd From: https://www.cnblogs.com/towboa/p/17232879.html