acwing 区间 gcd 线段树

区间gcd

题目链接

题目大意：

两种操作 ：
Q l r 查询 l~r 的区间gcd
C l r x 将l~r 区间的数都加上x

怎么做？ 我这tm都不会 好菜
想一下怎么求gcd？
辗转相减？
gcd(a,b) == gcd(a,b-a);
所以
gcd(a1,a2,a3,a4,……) == gcd(a1,a2-a1,a3-a2,a4-a3,……)
gcd(al,al+1,……) == gcd(al,al+1-al,……)
所以维护差分数组的gcd就好了
为什么维护差分数组呢
因为区间修改 可以改为 单点修改 这样维护gcd很舒服
维护一个差分数组 还得维护 一个a[l]的值 怎么维护？ 这个比较简单 一个树状数组像差分那样维护就好了
代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 5e5+5;

ll a[maxn];
ll b[maxn];
struct Node
{
   
	int l,r;
	ll num;
}node[maxn<<2];

ll gcd(ll a,ll b)
{
   
	return b == 0? a : gcd(b,a %b);
}
ll ad(ll a)
{
   
	return a > 0? a : -a;
}
void build(int l,int r,int no)
{
   
	node[no].l = l;
	node[no].r=r ;
	if(l == r)
	{
   
		node[no].num = b[l];
		return;
	}
	int mid = l + r >> 1;
	build(l,mid,no<<1);
	build(mid+1,r,no<<1|1);
	node[no].num = gcd(node[no<<1].num, node[no<<1|1].num);
 } 
void update(int x,int no,ll num)
{
   
	if(node[no].l == node[no].r)
	{
   
		node[no].num += num;
		return;
	}
	int mid = node[no].l + node[no].r >> 1;
	if(x <= mid) update(x,no<<1,num);
	else update(x,no<<1|1,num);
	node[no].num = gcd(node[no<<1].num, node[no<<1|1].num);
}

ll query(int l,int r,int no)
{
   
	if(node[no].l >= l && node[no].r <= r)
	{
   
		return  ad(node[no].num);
	}
	int mid = node[no].l + node[no].r >> 1;
	if(r <= mid) return ad(query(l,r,no<<1));
	if(l > mid) return ad(query(l,r,no<<1|1));
	return ad(gcd(query(l,r,no<<1),query(l,r,no<<1|1)));
}
int lowbit(int x)
{
   
	return x & (-x);
}
ll tree[maxn];
int n;
void add(int x,ll num)
{
   
	while(x <= n)
	{
   
		tree[x] += num;
		x += lowbit(x);
	}
}
ll getx(int x)
{
   
	ll ans = 0;
	while(x > 0)
	{
   
		ans += tree[x];
		x -= lowbit(x);
	}
	return ans;
}

int main()
{
   
	int m;
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; i ++ )
	{
   
		scanf("%lld",&a[i]);
	}
	for (int i = n; i >= 1; i -- )
	{
   
		b[i] = a[i] - a[i-1];
	}
	build(1,n,1);int l,r;
	
	while(m -- )
	{
   
		char t[2];
		scanf("%s",t);
		if(t[0] == 'Q')
		{
   
			scanf("%d%d",&l,&r);
			if(l == r)
			{
   
				printf("%lld\n",a[l] + getx(l));
				continue;
			}
			printf("%lld\n",gcd(ad(query(l+1,r,1)),ad(a[l] + getx(l))));
		}
		else
		{
   
			ll num;
			scanf("%d%d%lld",&l,&r,&num);
			update(l,1,num);
			if(r + 1 <= n)
				update(r + 1,1,-num);
			add(l,num);
			add(r + 1,-num);
		}
	}
 } 

我是真的菜。。。。。