rt，用线段树写，可以轻松水过；但在相同的思路下用分块，会 TLE on #12。

分块代码如下：

#include<iostream>
#include<cmath>
#define ll long long
#define INF 1e18
using namespace std;

const int N=1e5+5;
const int M=320;

namespace OIfast{
	
	char buf[1<<21],*p1,*p2,*top, buffer[1<<21];
	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?0:*p1++)
	
	inline ll read(){
		ll n=0,f=1;
		char c=getchar();
		while(c<'0'||c>'9'){
			if(c=='-')f=-1;
			c=getchar();
		}
		while(c>='0'&&c<='9'){
			n=(n<<3)+(n<<1)+(c^48);
			c=getchar();
		}
		return n*f;
	}
	
	inline void print(ll n){
		if(n<0)n=~n+1,putchar('-');
		if(n>=10)print(n/10);
		putchar(n%10^48);
		return ;
	}
	
	inline void write(ll n,char c){
		print(n),putchar(c);
		return ;
	}
	
}using namespace OIfast;

//namespace Math{
//	
//	ll gcd(ll a,ll b){
//		ll t=1,c,d;
//		while(a!=b){
//			if(!b)break;
//			if(a<b) swap(a,b);
//			if(!(a&1)){
//				a>>=1;
//				c=1;
//			}else c=0;
//			if(!(b&1)){
//				b>>=1;
//				d=1;
//			}else d=0;
//			if(c&&d) t<<1;
//			else if(!c&&!d)a-=b;
//		}
//		return t*a;
//	}
//	
//	inline ll lcm(ll a,ll b){
//		return a/gcd(a,b)*b;
//	}
//	
//}using namespace Math;

namespace FK{
	
	int n,m;
	int k,tot;
	
	int L[M],R[M];
	short loc[N];
	ll la[M]/*加*/,sum[M],maxx[M];
	ll a[N];
	
	inline void pushdown(int i){
		for(int j=L[i];j<=R[i];++j)a[j]+=la[i];
		la[i]=0;
		return ;
	}
	
	inline void add(int i){
		sum[i]=0;
		for(int j=L[i];j<=R[i];++j)sum[i]+=a[j];
		return ;
	}
	
	inline void modify(int i){
		maxx[i]=-INF;
		for(int j=L[i];j<=R[i];++j)maxx[i]=max(maxx[i],a[j]);
		return ;
	}
	
	inline void init(){
		k=sqrt(n);
		if(k*k<n)tot=k+1;
		else tot=k;
		for(int i=1;i<=tot;++i){
			L[i]=(i-1)*k+1;
			if(i==tot)R[i]=n;
			else R[i]=L[i]+k-1;
			add(i),modify(i);
		}
		return ;
	}
	
	inline void upd1(int tar,ll v){//加
		pushdown(loc[tar]);
		a[tar]=v;
		add(loc[tar]),modify(loc[tar]);
		return ;
	}
	
	inline void upd2(int l,int r,ll v){//模
		if(loc[l]==loc[r]){
			pushdown(loc[l]);
			for(int i=l;i<=r;++i)a[i]%=v;
			add(loc[l]),modify(loc[l]);
		}else{
			pushdown(loc[l]),pushdown(loc[r]);
			for(int i=l;i<=R[loc[l]];++i)a[i]%=v;
			for(int i=L[loc[r]];i<=r;++i)a[i]%=v;
			add(loc[l]),add(loc[r]),modify(loc[l]),modify(loc[r]);
			for(int i=loc[l]+1;i<=loc[r]-1;++i){
				if(maxx[i]<v)continue ;
				pushdown(i);
				for(int j=L[i];j<=R[i];++j)a[j]%=v;
				add(i),modify(i);
			}
		}
		return ;
	}
	
	inline ll qry(int l,int r){
		ll res=0;
		if(loc[l]==loc[r]){
			pushdown(loc[l]);
			for(int i=l;i<=r;++i)res+=a[i];
		}else{
			pushdown(loc[l]),pushdown(loc[r]);
			for(int i=l;i<=R[loc[l]];++i)res+=a[i];
			for(int i=L[loc[r]];i<=r;++i)res+=a[i];
			for(int i=loc[l]+1;i<=loc[r]-1;++i)res+=sum[i];
		}
		return res;
	}
	
}using namespace FK;

inline void work(){
	int op=read(),l=read(),r;
	if(1==2){
		puts("wow");
	}else if(op==1){
		r=read();
		write(qry(l,r),'\n');
	}else if(op==2){
		r=read();
		ll x=read();
		upd2(l,r,x);
	}else if(op==3){
		ll x=read();
		upd1(l,x);
	}
	return ;
}

signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i)a[i]=read();
	init();
	while(m--)work();
	return 0;
}

#undef ll
#undef INF