Description：

单点赋值 $+$ 区间取模 $+$ 区间求和

$1\le n \le 10^5$

Solution：

若模数 $>\frac x 2$ ，则模完之后小于 $\frac x 2$ ，若模数 $<\frac x 2$ ，则模完之后小于 $\frac x 2$ ，所以一个数最多模 $log_2 n$ 次就成了 $0$ ，于是就能用线段树暴力维护了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

int a[MAXN];

#define mid ((l + r) >> 1)

struct node

{

	int lc,rc,max;

	long long sum;

	node(){sum = 0ll;max = 0;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

void pushup(int rt)

{

	t[rt].max = max(t[t[rt].lc].max,t[t[rt].rc].max);

	t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;

	return;

}

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)

	{

		t[rt].sum = t[rt].max = a[l];

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	pushup(rt);

	return;

}

long long query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].sum;

	long long res = 0;

	if(L <= mid)res += query(t[rt].lc,L,R,l,mid);

	if(R > mid)res += query(t[rt].rc,L,R,mid + 1,r);

	return res;

}

void module(int rt,int L,int R,int k,int l,int r)

{

	if(t[rt].max < k)return;

	if(l == r)

	{

		t[rt].sum = t[rt].max = t[rt].sum % k;

		return;

	}

	if(L <= mid)module(t[rt].lc,L,R,k,l,mid);

	if(R > mid)module(t[rt].rc,L,R,k,mid + 1,r);

	pushup(rt);

	return;

}

void set(int rt,int p,int k,int l,int r)

{

	if(l == r)

	{

		t[rt].sum = t[rt].max = k;

		return;

	}

	if(p <= mid)set(t[rt].lc,p,k,l,mid);

	else set(t[rt].rc,p,k,mid + 1,r);

	pushup(rt);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

		scanf("%d",&a[i]);

	build(root,1,n);

	int x,a,b,c;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&x);

		if(x == 1)

		{

			scanf("%d%d",&a,&b);

			printf("%I64d\n",query(root,a,b,1,n));

		}

		if(x == 2)

		{

			scanf("%d%d%d",&a,&b,&c);

			module(root,a,b,c,1,n);

		}

		if(x == 3)

		{

			scanf("%d%d",&a,&b);

			set(root,a,b,1,n);

		}

	}

	return 0;

}