C27 线段树 区间最大公约数

/*
gcd(x,y)=gcd(x,y-x)
gcd(x,y,z)=gcd(x,y-x,z-y)
……
所以设B[i]=A[i]-A[i-1]
求gcd(A[L]……A[R])等价于求gcd(A[L],gcd(B[L+1],…,B[R]))
即： gcd( A[L] , gcd(B[L+1]…B[R]) )
线段树维护的是B数组。 
1、修改区间[L,R]对每个A[x]都有影响：维护c数组，b[1]+b[2]+…+b[x] 为 A[x]现在的值 
2、修改区间[L,R]并不是对每个B[x]都有影响：只需要修改B[L]+k,B[R+1]-k
*/
#include <bits/stdc++.h>
using namespace std;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
typedef long long LL;
const int N=5e5+10;
struct trnode{int l,r;LL s,d;}tr[N*4];LL a[N],b[N];int n,m;
void merge(trnode &t,trnode l,trnode r)
{
	t.s=l.s+r.s;
	t.d=__gcd(l.d,r.d);
}
void bt(int p,int l,int r)
{
	tr[p]=trnode{l,r,0,0};
    if(l==r){tr[p].s=tr[p].d=b[l];return; }
	int m=(l+r)/2;
	bt(lc(p),l,m);bt(rc(p),m+1,r);
	merge(tr[p],tr[lc(p)],tr[rc(p)]);
}
void change(int p,int x,LL k)
{
    if(x<tr[p].l || tr[p].r<x) return ;
	if(tr[p].l==tr[p].r){tr[p].s+=k;tr[p].d+=k;return;}
	change(lc(p),x,k);change(rc(p),x,k);
	merge(tr[p],tr[lc(p)],tr[rc(p)]);
}
trnode query(int p,int l,int r)
{
    if(r<tr[p].l || tr[p].r<l) return {0,0,0,0};
	if(l<=tr[p].l && tr[p].r<=r)return tr[p];
	trnode t;
    merge(t,query(lc(p),l,r),query(rc(p),l,r));
	return t;
}
int main()
{
	scanf("%d%d",&n,&m);
	a[0]=0;for(int i=1;i<=n;i++)scanf("%lld",&a[i]),b[i]=a[i]-a[i-1];
	bt(1,1,n+1);
	for (int i=1,l,r;i<=m;i++)
	{
		char s[2];scanf("%s%d%d",s,&l,&r);
		if(s[0]=='Q')
		{
			printf("%lld\n",abs(__gcd( query(1,1,l).s,query(1,l+1,r).d )) );
		}
		else
		{
			LL k;scanf("%lld", &k);
			change(1,l,k);
			change(1,r+1,-k);
		}
	}
	return 0;
}

C27 线段树 区间最大公约数

/*
gcd(x,y)=gcd(x,y-x)
gcd(x,y,z)=gcd(x,y-x,z-y)
……
所以设B[i]=A[i]-A[i-1]
求gcd(A[L]……A[R])等价于求gcd(A[L],B[L+1],……B[R])
即： gcd( A[L] , gcd(B[L+1],…,B[R]) )
线段树维护的是B数组。
1、修改区间[L,R]对每个A[x]都有影响：维护c数组，b[1]+b[2]+…+b[x] 为 A[x]现在的值
2、修改区间[L,R]并不是对每个B[x]都有影响：只需要修改B[L]+k,B[R+1]-k
/
#include<bits/stdc++.h>
using namespace std;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
typedef long long LL;
const int N=5e5+10;
struct trnode{int l,r;LL s,d;}tr[N4];LL a[N],b[N];int n, m;
void merge(trnode &t,trnode l,trnode r)
{
t.s=l.s+r.s;
t.d=__gcd(l.d,r.d);
}
void bt(int p, int l, int r)
{
tr[p]=trnode{l,r,0,0};
if(lr){tr[p].s=tr[p].d=b[l];return; }
int m=(l+r)/2;
bt(lc(p),l,m);bt(rc(p),m+1,r);
merge(tr[p],tr[lc(p)],tr[rc(p)]);
}
void change(int p, int x, LL k)
{
if(x<tr[p].l || tr[p].r<x) return ;
if(tr[p].ltr[p].r){tr[p].s+=k;tr[p].d+=k;return;}
change(lc(p),x,k);change(rc(p),x,k);
merge(tr[p],tr[lc(p)],tr[rc(p)]);
}
trnode query(int p, int l, int r)
{
if(r<tr[p].l || tr[p].r<l) return {0,0,0,0};
if(l<=tr[p].l && tr[p].r<=r)return tr[p];
trnode t;
merge(t,query(lc(p),l,r),query(rc(p),l,r));
return t;
}
int main()
{
scanf("%d%d",&n,&m);
a[0]=0;for(int i=1;i<=n;i++)scanf("%lld",&a[i]),b[i]=a[i]-a[i-1];
bt(1,1,n+1);
for (int i=1,l,r;i<=m;i++)
{
char s[2];scanf("%s%d%d",s,&l,&r);
if(s[0]=='Q')
{
printf("%lld\n",abs(__gcd( query(1,1,l).s,query(1,l+1,r).d ) )  );
}
else
{
LL k;scanf("%lld", &k);
change(1,l,k);
change(1,r+1,-k);
}
}
return 0;
}