CF438D TLE on #39 求条

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int sum[N<<2],mx[N<<2];
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
void pushup(int p)
{
	sum[p]=sum[ls(p)]+sum[rs(p)];
	mx[p]=mx[ls(p)]+mx[rs(p)];
}
void pupdate(int p,int pl,int pr,int x,int d)
{
	if(pl==x&&pr==x)
	{
		sum[p]=mx[p]=d;
		return ;
	}
	if(pr<x||pl>x)
		return ;
	int mid=pl+pr>>1;
	pupdate(ls(p),pl,mid,x,d);
	pupdate(rs(p),mid+1,pr,x,d);
	pushup(p);
}
void rupdate(int p,int pl,int pr,int l,int r,int mod)
{
	if(r<pl||pr<l||mx[p]<mod)
		return ;
	if(pl==pr)
	{
		sum[p]%=mod;
		mx[p]%=mod;
		return ;
	}
	int mid=pl+pr>>1;
	rupdate(ls(p),pl,mid,l,r,mod);
	rupdate(rs(p),mid+1,pr,l,r,mod);
	pushup(p);
}
int query(int p,int pl,int pr,int l,int r)
{
	if(l<=pl&&pr<=r)
		return sum[p];
	if(r<pl||pr<l)
		return 0;
	int mid=pl+pr>>1;
	return query(ls(p),pl,mid,l,r)+query(rs(p),mid+1,pr,l,r);
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		int tmp;
		cin>>tmp;
		pupdate(1,1,n,i,tmp); 
	}
	while(m--)
	{
		int op,l,r,mod;
		cin>>op>>l>>r;
		if(op==1)
			cout<<query(1,1,n,l,r)<<'\n';
		if(op==2)
		{
			cin>>mod;
			rupdate(1,1,n,l,r,mod);
		}
		if(op==3)
			pupdate(1,1,n,l,r);
	}
		
}