【算法】数学+线段树/树状数组
【题解】
首先三个操作可以理解为更相减损术或者辗转相除法（待证明），所以就是求区间gcd。
这题的问题在线段树维护gcd只能支持修改成一个数，不支持加一个数。
套路：gcd(a,b,c,d,e)=gcd(a-b,b-c,c-d,d-e,e)，也就是所有数的gcd可以转化为所有差值和最后一个数的gcd。
那么只需要查询区间差值gcd和一个数。
对于区间差值gcd查询，区间加数只会导致两个单位的差值变化，所以可以用线段树单点修改区间查询gcd。
对于一个数查询，就用树状数组维护区间加值和单点查询就行了。
#include#include #include #include #define lowbit(x) x&(-x)using namespace std;const int maxn=100010;struct tree{ int l,r,g;}t[maxn*4];int a[maxn],c[maxn],n,m;int read(){ char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t;}int gcd(int a,int b){ return !b?a:gcd(b,a%b);}void modify(int x,int k){ for(int i=x;i<=n;i+=lowbit(i))c[i]+=k;}int query(int x){ int as=0;for(int i=x;i>=1;i-=lowbit(i))as+=c[i];return as;}//as给初值 void build(int k,int l,int r){ t[k].l=l;t[k].r=r; if(l==r)t[k].g=a[l]-a[l+1]; else{ int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); t[k].g=gcd(t[k<<1].g,t[k<<1|1].g); }}void add(int k,int x,int v){ if(t[k].l==t[k].r)t[k].g+=v; else{ int mid=(t[k].l+t[k].r)>>1; if(x<=mid)add(k<<1,x,v); else add(k<<1|1,x,v); t[k].g=gcd(t[k<<1].g,t[k<<1|1].g); }}int ask(int k,int l,int r){ if(l<=t[k].l&&t[k].r<=r)return t[k].g; else{ int mid=(t[k].l+t[k].r)>>1,x1=0,x2=0; if(l<=mid)x1=ask(k<<1,l,r); if(r>mid)x2=ask(k<<1|1,l,r); if(x1&&x2)return gcd(x1,x2); if(x1)return x1; return x2; }} int ab(int x){ return x>0?x:-x;}int main(){ n=read();m=read(); a[0]=0; for(int i=1;i<=n;i++)a[i]=read(),modify(i,a[i]-a[i-1]); a[n+1]=1; build(1,1,n); for(int i=1;i<=m;i++){ int p=read(),l=read(),r=read(); if(l>r)swap(l,r); if(p==1){ if(l==r)printf("%d\n",query(r)); else printf("%d\n",ab(gcd(ask(1,l,r-1),query(r))));//gcd不怕0 } else{ int v=read(); if(l>1)add(1,l-1,-v);//注意边界！ add(1,r,v); modify(l,v); if(r