AcWing 246. 区间最大公约数----线段树 + 差分模板题

debug1个多小时.......

线段树 + 差分模板题
差分模板可以参考 AcWing 797. 差分

线段树的详细模板可以参考 AcWing 1275. 最大数

思路

第一个操作：

        因为涉及到了区间修改的问题，直观上需要pushdown操作，即用父节点信息来更新子节点信息，但是pushdown操作很复杂并且容易写错，所以使用差分数组的技巧：

                设原数组第i为的值为a[i]，差分数组b：b[i]=a[i]-a[i-1]

第二个操作：

        根据"更相减损术"

        则有gcd(a,b)=gcd(a,b-a)

        推广得到：

        gcd(a,b,c)=((a,b),(b,c))=(a,b-a,c-b)

        那么我们发现了一个规律：

        （a[l],.......a[r]）这个区间的最大公约是为

          (a[l],a[l+1]-a[l]....a[r]-a[r-1])

        可以得到(a[l],b[l+1].......b[r])

        那么问题转化为差分数组b[l+1],b[r]这个区间的最大公约数与a[l]的最大公约数

        （因为线段树维护的是b数组，b[l+1]~b[r]这个区间的最大公约数query一下就行了)

#include<bits/stdc++.h>
#define int long long
using namespace std;
 
const int N=5e5+10;
 
int n,m;
int w[N];
struct node {
	int l,r,sum,d;
} t[N*4];
 
int  gcd(int a,int b) {
	return b ? gcd(b,a % b) : a;
}
 
void pushup(node &u,node &left,node &right) {
	u.sum = left.sum + right.sum;
	//cout<<u.l<<" "<<u.r<<" "<<u.sum<<endl;
	u.d = gcd(left.d,right.d);
}
 
void pushup(int u) { //重载一下pushup,可以省去一点步骤
	pushup(t[u],t[u << 1],t[u << 1 | 1]);
}
 
void build(int u,int l,int r) { //维护的是一个差分数组
	if(l == r) {
		int d = w[r] - w[r - 1];
		t[u] = {l,r,d,d};;
	} else {
		t[u].r = r, t[u].l = l;
		int mid = l + r >> 1;
		build(u << 1,l,mid);
		build(u << 1 | 1,mid + 1,r);
		pushup(u);
	}
}
 
 
void modify(int u,int x,int v) {
	if(t[u].l==x&&t[u].r==x) {
		int b=t[u].sum+v;
		t[u]= {x,x,b,b};
	} else {
		int mid=t[u].l+t[u].r>>1;
		if(x<=mid) {
			modify(u<<1,x,v);
		} else {
			modify(u<<1|1,x,v);
		}
		pushup(u);
	}
}
 
node query(int u,int l,int r) {
	if(t[u].l>=l&&t[u].r<=r)
		return t[u];
	else {
		int mid=t[u].l+t[u].r>>1;
		if(r<=mid) {
			return query(u<<1,l,r);
		} else if(l>mid) {
			return query(u<<1|1,l,r);
		} else {
			node res;
			auto left =query(u<<1,l,r);
			auto right=query(u<<1|1,l,r);
			pushup(res,left,right);
			return res;
		}
	}
 
}
 
signed main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		cin>>w[i];
	}
 
	build(1,1,n);
	int l,r;
	char op[2];
 
	while(m--) {
		scanf("%s%lld%lld",op,&l,&r);
		if(*op=='C') {
			int d;
			cin>>d;
			modify(1,l,d);
			if (r + 1 <= n)
				modify(1,r + 1,-d);
		} else {
			node left=query(1,1,l);
			node right({0,0,0,0});
			if(l+1<=r) {
				right=query(1,l+1,r);
				//b[l + 1 ~ r]的最大公约数，
				//就相当于(A[l+1]-A[l] ,
				//A[l+2]-A[l+1] , A[l+3]-A[l+2] ,
				//... , A[r]-A[r-1])的最大公约数
			}
			//cout<<left.sum<<' '<<right.d<<endl;
			int res = abs(gcd(left.sum,right.d));  //约定最大公约数是没有负数的，所以遇到附属就把他取反
			printf("%lld\n",res);
		}
	}
	return 0;
}
/*