TLE on 39。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;

int n,m;
int a[N];
namespace segmenttree{
	ll tr[N << 2];
	ll maxn[N << 2];
	#define ls u << 1
	#define rs u << 1 | 1
	#define mid ((l + r) >> 1)
	inline void push_up(int u){tr[u] = tr[ls] + tr[rs],maxn[u] = max(tr[ls],tr[rs]);}
	inline void build(int u,int l,int r){
		tr[u] = maxn[u] = 0;
		if (l == r) return tr[u] = maxn[u] = (ll)a[l],(void)0;
		build(ls,l,mid);build(rs,mid + 1,r);push_up(u);
	}
	inline void modify_p(int u,int l,int r,int ql,int qr,int p){
		if (maxn[u] < p) return;
		if (l == r) return tr[u] = tr[u] % p,maxn[u] %= p,(void)0;
		if (ql <= mid) modify_p(ls,l,mid,ql,qr,p);if (qr > mid) modify_p(rs,mid + 1,r,ql,qr,p);push_up(u);
	}
	inline void modify(int u,int l,int r,int ql,int qr,int x){
		if (l == r) return tr[u] = maxn[u] = (ll)x,(void)0;
		if (ql <= mid) modify(ls,l,mid,ql,qr,x);else modify(rs,mid + 1,r,ql,qr,x);push_up(u);
	}
	inline ll query(int u,int l,int r,int ql,int qr){
		if (ql <= l && r <= qr) return tr[u];
		ll ans = 0;if (ql <= mid) ans += query(ls,l,mid,ql,qr);if (qr > mid) ans += query(rs,mid + 1,r,ql,qr);return ans;
	}
}using namespace segmenttree;
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> n >> m;for (int i = 1;i <= n;i++) cin >> a[i];
	build(1,1,n);
	for (int i = 1,l,r,op,p;i <= m;i++){
		cin >> op >> l >> r;
		if (op == 1) cout << query(1,1,n,l,r) << "\n";
		else if (op == 2) cin >> p,modify_p(1,1,n,l,r,p);
		else modify(1,1,n,l,l,r);
	}
}