自动搬运

查看原文

来自洛谷，原作者为

	mlvx 喵

搬运于2025-08-24 22:58:11，当前版本为作者最后更新于2024-07-16 17:29:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

区间加，求区间最大公约数。

分析

先考虑本题的单点加形式。

挺简单的，直接在线段树上维护区间最大公约数即可。

那如何把区间加转化成单点加呢？

差分。

线段树每个叶子节点都表示一个差分后的值。

为什么差分之后的最大公约数和原来的是一样的呢？

易知 $\gcd\{a\}=\gcd\{\gcd(a_1,a_2),\gcd(a_2,a_3),\dots,\gcd(a_{n-1},a_{n})\}$。

又由 $\gcd(x,y)=\gcd(x,y-x)$ 得 $\gcd\{a\}=\gcd\{\gcd(a_1,a_2-a_1),\gcd(a_2,a_3-a_2),\dots,\gcd(a_{n-1},a_n-a_{n-1})\}$。

整理一下又得 $\gcd\{a\}=\gcd\{a_1,a_2-a_1,a_2,a_3-a_2,\dots,a_{n-1},a_n-a_{n-1}\}$。

发现 $a_2,a_3,\dots,a_{n-1}$ 都被两边的项给囊括了，所以这些都可以不要。

也就得到了 $\gcd\{a\}=\gcd\{a_1,a_2-a_1,a_3-a_2,\dots,a_n-a_{n-1}\}$。

最后，由于是差分数组的最大公约数，区间公约数还要带上一个 $a_l$，可以线段树上再维护一个和，也可以再搞个树状数组，查询的时候就是 $\gcd\{a_l,\gcd_{i=l+1}^r a_i-a_{i-1}\}$。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pl (p<<1)
#define pr (p<<1|1)
const int N=5e5+10;
struct Tree{ll sum,gcd;}tr[N<<2];
int n,q,l,r;ll v,a[N];char op;
void push_up(int p){tr[p]={tr[pl].sum+tr[pr].sum,__gcd(tr[pl].gcd,tr[pr].gcd)};}//上放标记
void build(int l,int r,int p){//建树
	if(l==r)return tr[p]={a[l]-a[l-1],a[l]-a[l-1]},void();//将差分存进去
	int mid=l+r>>1;
	build(l,mid,pl),build(mid+1,r,pr),push_up(p);
}void update(int l,int r,int k,ll v,int p){//单点加
	if(l==r)return tr[p].sum+=v,tr[p].gcd+=v,void();
	int mid=l+r>>1;
	if(k<=mid)update(l,mid,k,v,pl);
	else update(mid+1,r,k,v,pr);
	push_up(p);
}ll query_sum(int l,int r,int le,int ri,int p){//区间和
	if(l>=le&r<=ri)return tr[p].sum;
	int mid=l+r>>1;ll ret=0;
	if(le<=mid)ret+=query_sum(l,mid,le,ri,pl);
	if(ri>mid)ret+=query_sum(mid+1,r,le,ri,pr);
	return ret;
}ll query_gcd(int l,int r,int le,int ri,int p){//区间最大公约数
	if(l>=le&r<=ri)return tr[p].gcd;
	int mid=l+r>>1;ll ret=0;
	if(le<=mid)ret=__gcd(ret,query_gcd(l,mid,le,ri,pl));
	if(ri>mid)ret=__gcd(ret,query_gcd(mid+1,r,le,ri,pr));
	return ret;
}int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,n,1);
	while(q--){
		cin>>op>>l>>r;
		if(op=='C')cin>>v,update(1,n,l,v,1),r!=n&&(update(1,n,r+1,-v,1),1);
		else cout<<abs(__gcd(query_gcd(1,n,l+1,r,1),query_sum(1,n,1,l,1)))<<'\n';//记得取绝对值
	}return 0;
}