rt，这是我的代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long long
const int MAXN=1e5+5;
const int MAXM=2e3+5;
int n;
int a[MAXN];
int l[MAXM];
int r[MAXM];
int pos[MAXN];
int lazy[MAXM];
int sum[MAXN];
int maxn[MAXM];
int size;
int m;
void pre(){
	size=sqrt(n);
	m=ceil(1.0*n/size);
	for(int i=1;i<=m;i++){
		l[i]=r[i-1]+1;
		r[i]=i*size;
	} 
	r[m]=n;
	for(int i=1;i<=n;i++){
		pos[i]=(i-1)/size+1;
	}
	for(int i=1;i<=n;i++){
		sum[pos[i]]+=a[i];
		maxn[pos[i]]=max(maxn[pos[i]],a[i]);
	}
}
void update(int L,int R,int p){
	for(int i=L;i<=R;i++){
		a[i]%=p;
	}
	maxn[pos[L]]=0;
	sum[pos[L]]=0;
	for(int i=l[pos[L]];i<=r[pos[L]];i++){
		maxn[pos[L]]=max(maxn[pos[L]],a[i]);
		sum[pos[L]]+=a[i];
	}
} 
void mod(int ql,int qr,int p){
	if(pos[ql]==pos[qr]){
		update(ql,qr,p);
	}
	else{
		update(ql,r[pos[ql]],p);
		update(l[pos[qr]],qr,p);
		for(int i=pos[ql]+1;i<=pos[qr]-1;i++){
			if(maxn[i]>=p){
				update(l[i],r[i],p);
			} 
		}
	}
}
void add(int x,int k){
	sum[pos[x]]-=a[x];
	a[x]=k;
	sum[pos[x]]+=a[x];
	maxn[pos[x]]=0;
	for(int i=l[pos[x]];i<=r[pos[x]];i++){
		maxn[pos[x]]=max(maxn[pos[x]],a[i]);
	}
}
int query(int ql,int qr){
	if(pos[ql]==pos[qr]){
		int s=0;
		for(int i=ql;i<=qr;i++){
			s+=a[i];
		} 
		return s;
	}
	int s=0;
	for(int i=ql;i<=r[pos[ql]];i++){
		s+=a[i];
	}
	for(int i=pos[ql]+1;i<=pos[qr]-1;i++){
		s+=sum[i];
	} 
	for(int i=l[pos[qr]];i<=qr;i++){
		s+=a[i];
	} 
	return s;
}
signed main(){
	int M;
	scanf("%lld %lld",&n,&M);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	pre();
	for(int i=1;i<=M;i++){
		int type;
		scanf("%lld",&type);
		if(type==1){
			int l,r;
			scanf("%lld %lld",&l,&r);
			printf("%lld\n",query(l,r));
		}
		if(type==2){
			int l,r,x;
			scanf("%lld %lld %lld",&l,&r,&x);
			mod(l,r,x);
		}
		if(type==3){
			int k,x;
			scanf("%lld %lld",&k,&x);
			add(k,x);
		}
	}
return 0;
}