题意：
给定一个长度为n的非负整数序列a，你需要支持以下操作：
1）给定l，r，输出a[l] + a[l+1] + ... + a[r]
2）给定l，r，x， 将a[l]、a[l+1]、....、a[r]对x取模
3）给定k，y，将a[k]修改为y
n, m <= 100000，a[i], x, y <= 10
对于操作（1）（3）非常简单，线段树基本操作
问题是操作（2），显然的是我们不能对区间和取模，这样就很难受
但是我们可以想到，一个数若是比模数小，就不需要取模，而一个数w有效取模次数最多为log(w)
同时单个数被有效取模的一次只会花费O(logn)
因此每次修改至多使复杂度增加O(lognlogw)
这样我们对于区间l, r暴力对每个能取模的数取模即可
最后时间复杂度为O(mlognlogw)
#include<bits/stdc++.h>
#define ll long long
#define uint unsigned int
#define ull unsigned long long
using namespace std;
const int maxn = ;
struct shiki {
ll maxx, sum;
}tree[maxn << ];
int n, m;
ll a[maxn]; inline ll read() {
ll x = , y = ;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') y = -;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << ) + (x << ) + ch - '';
ch = getchar();
}
return x * y;
} inline void maintain(int pos) {
int ls = pos << , rs = pos << | ;
tree[pos].maxx = max(tree[ls].maxx, tree[rs].maxx);
tree[pos].sum = tree[ls].sum + tree[rs].sum;
} void build(int pos, int l, int r) {
if(l == r) {
tree[pos].maxx = tree[pos].sum = a[l];
return;
}
int mid = l + r >> ;
build(pos << , l, mid);
build(pos << | , mid + , r);
maintain(pos);
} void get_mod(int pos, int L, int R, int l, int r, ll mod) {
if(l > R || r < L) return;
if(tree[pos].maxx < mod) return;
if(l == r) {
tree[pos].sum %= mod;
tree[pos].maxx %= mod;
return;
}
int mid = l + r >> ;
get_mod(pos << , L, R, l, mid, mod);
get_mod(pos << | , L, R, mid + , r, mod);
maintain(pos);
} void update(int pos, int aim, int l, int r, ll val) {
if(l == r && l == aim) {
tree[pos].maxx = tree[pos].sum = val;
return;
}
int mid = l + r >> ;
if(aim <= mid) update(pos << , aim, l, mid, val);
else update(pos << | , aim, mid + , r, val);
maintain(pos);
} ll query_sum(int pos, int L, int R, int l, int r) {
if(l > R || r < L) return ;
if(l >= L & r <= R) return tree[pos].sum;
int mid = l + r >> ;
return query_sum(pos << , L, R, l, mid) + query_sum(pos << | , L, R, mid + , r);
} int main() {
n = read(), m = read();
for(int i = ; i <= n; ++i) a[i] = read();
build(, , n);
for(int i = ; i <= m; ++i) {
int opt = read(), x = read(), y = read();
if(opt == ) printf("%I64d\n", query_sum(, x, y, , n));
if(opt == ) {
ll p = read();
get_mod(, x, y, , n, p);
}
if(opt == ) update(, x, , n, y);
}
return ;
}