C++14(g++5.4) 解法, 执行用时: 103ms, 内存消耗: 5920K, 提交时间: 2020-07-09 10:40:06

#include<bits/stdc++.h>
using namespace std;
const int mx=4e5+5;
int s[mx],t[mx],d[mx],a[100005];
inline void work(int p){
	s[p]=s[p*2]+s[p*2+1];
	t[p]=max(t[p*2],t[p*2+1]);
	d[p]=__gcd(d[p*2],d[p*2+1]);
}
void build(int p,int l,int r){
	if(l==r){
		s[p]=a[l],t[p]=d[p]=abs(a[l]);
		return;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid),build(p*2+1,mid+1,r);
	work(p);
}
void change(int p,int l,int r,int x){
	if(l==r){
		s[p]=a[l],t[p]=d[p]=abs(a[l]);
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)change(p*2,l,mid,x);
	else change(p*2+1,mid+1,r,x);
	work(p);
}
int query(int p,int l,int r,int x,int y){
	if(x<=l&&r<=y)return t[p];
	int mid=(l+r)>>1,a1=0,a2=0;
	if(x<=mid)a1=query(p*2,l,mid,x,y);
	if(mid<y)a2=query(p*2+1,mid+1,r,x,y);
	return max(a1,a2); 
}
int get(int p,int l,int r,int x,int y){
	if(x<=l&&r<=y)return s[p];
	int mid=(l+r)>>1,re=0;
	if(x<=mid)re+=get(p*2,l,mid,x,y);
	if(mid<y)re+=get(p*2+1,mid+1,r,x,y);
	return re;
}
int find(int p,int l,int r,int x,int y){
	if(x<=l&&r<=y)return d[p];
	int mid=l+r>>1,a1=0,a2=0;
	if(x<=mid)a1=find(p*2,l,mid,x,y);
	if(mid<y)a2=find(p*2+1,mid+1,r,x,y);
	return __gcd(a1,a2);
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",a+i);
	for(int i=n;i;--i)a[i]-=a[i-1];
	build(1,1,n);
	int op,l,r,x;
	while(m--){
		scanf("%d%d%d",&op,&l,&r);
		if(op==1){
			scanf("%d",&x);
			a[l]+=x,change(1,1,n,l);
			if(r+1<=n)a[r+1]-=x,change(1,1,n,r+1); 
		}
		else if(op==2){
			if(l==r)puts("0");
			else printf("%d\n",query(1,1,n,l+1,r)); 
		}
		else printf("%d\n",__gcd(get(1,1,n,1,l),find(1,1,n,l+1,r)));
	}
}

C++(clang++ 11.0.1) 解法, 执行用时: 149ms, 内存消耗: 4120K, 提交时间: 2022-09-14 01:12:19

#include<bits/stdc++.h> 
#define ls (x<<1)
#define rs (x<<1|1)
using namespace std;
const int N=1e5+5; int n,v[N];
struct Seg{
	int s,m,t;
	inline Seg operator +(const Seg &z) const{return {s+z.s,max(m,z.m),__gcd(t,z.t)};}
}a[N<<2];
void pushup(int x) {a[x]=a[ls]+a[rs];}
void build(int x,int l,int r) {
	if (l==r) return a[x]={v[l],abs(v[l]),v[l]},void(); int mid=l+r>>1;
	build(ls,l,mid),build(rs,mid+1,r),pushup(x);
}
void update(int x,int l,int r,int p) {
	if (l==r) return a[x]={v[l],abs(v[l]),v[l]},void(); int mid=l+r>>1;
	if (p<=mid) update(ls,l,mid,p); else update(rs,mid+1,r,p); pushup(x);
}
Seg query(int x,int l,int r,int p,int q) {
	if (p>q) return {0,0,0};
	if (p<=l&&r<=q) return a[x]; int mid=l+r>>1;
	if (q<=mid) return query(ls,l,mid,p,q);
	else if (mid<p) return query(rs,mid+1,r,p,q);
	else return query(ls,l,mid,p,q)+query(rs,mid+1,r,p,q);
}
int main() {
	int T,i,x,y=0,z,q;
	scanf("%d%d",&n,&T);
	for (i=1;i<=n;i++) scanf("%d",v+i);
	for (i=n;i>1;i--) v[i]-=v[i-1];
	build(1,1,n);
	for (;T--;) {
		scanf("%d%d%d",&q,&x,&y);
		if (q==1) {
			scanf("%d",&z);
			v[x]+=z,update(1,1,n,x);
			if (y<n) v[y+1]-=z,update(1,1,n,y+1);
		}
		if (q==2) printf("%d\n",query(1,1,n,x+1,y).m);
		if (q==3) printf("%d\n",abs(__gcd(query(1,1,n,1,x).s,query(1,1,n,x+1,y).t)));
	}
}