RT，加了最大值优化就WA，不加就TLE。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define dep(i,r,l) for(int i=r;i>=l;i--) 
using namespace std;
const int N=1e5+5;
int n,m;
int a[N];
struct node{
	int L,R,MAX;
	ll data;
}t[4*N];
int read(){
	int k=0,x=0;
	char s=getchar();
	while(s<'0'||s>'9'){
		k|=s=='-';
		s=getchar();
	}
	while(s>='0'&&s<='9'){
		x=(x<<3)+(x<<1)+(s^48);
		s=getchar();
	}
	return k?-x:x;
}
void pushup(int p){
	t[p].data=t[p*2].data+t[p*2+1].data;
	t[p].MAX=max(t[p*2].MAX,t[p*2+1].MAX);
}
void build(int p,int l,int r){
	t[p].L=l,t[p].R=r;
	if(l==r){
		t[p].data=t[p].MAX=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	pushup(p);
}
ll ask(int p,int l,int r){
	if(t[p].L>=l && t[p].R<=r) return t[p].data;
	int mid=(t[p].L+t[p].R)/2;
	ll ans=0;
	if(l<=mid) ans=ask(p*2,l,r);
	if(r>mid) ans+=ask(p*2+1,l,r);
	return ans;
}
int zd(int p,int l,int r){
	if(t[p].L>=l && t[p].R<=r) return t[p].MAX;
	int mid=(t[p].L+t[p].R)/2,ans=0;
	if(l<=mid) ans=zd(p*2,l,r);
	if(r>mid) ans=max(zd(p*2+1,l,r),ans);
	return ans;
}
void change(int p,int x,int v){
	if(t[p].L==t[p].R){
		t[p].data=v;
		return ;
	}
	int mid=(t[p].L+t[p].R)/2;
	if(x<=mid) change(p*2,x,v);
	else change(p*2+1,x,v);
	pushup(p);
}
int main(){
	n=read(),m=read();
	rep(i,1,n) a[i]=read();
	build(1,1,n);
	while(m--){
		int opt,x,y,k;
		opt=read(),x=read(),y=read();
		if(opt==1) printf("%lld\n",ask(1,x,y));
		if(opt==2){
			k=read();
			if(zd(1,x,y)<k) continue;
			rep(i,x,y){
				int u=ask(1,i,i);
				if(u>=k) change(1,i,u%k);
			}
		}
		if(opt==3) change(1,x,y);
	}
	return 0;
}