这道题的思路有点像这篇博客
用线段树维护区间和、区间最大值。若区间最大值小于模数，则直接返回，不对此区间进行操作
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <cmath>
#define LL long long
#define ls p << 1
#define rs p << 1 | 1
#define mid ((l+r) >> 1)
using namespace std;
LL read() {
LL k = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
k = k * 10 + c - 48, c = getchar();
return k * f;
}
int n, q;
LL a[100010];
struct zzz {
int l, r;
LL maxx, sum;
}tree[100010 << 2];
inline void up(int p) {
tree[p].sum = tree[ls].sum + tree[rs].sum;
tree[p].maxx = max(tree[ls].maxx, tree[rs].maxx);
}
void build(int l, int r, int p) {
tree[p].l = l, tree[p].r = r;
if(l == r) {
tree[p].maxx = tree[p].sum = a[l];
return ;
}
build(l, mid, ls); build(mid+1, r, rs);
up(p);
}
void upmod(int nl, int nr, int p, LL k) {
if(tree[p].maxx < k) return ;
int l = tree[p].l, r = tree[p].r;
if(l == r) {
tree[p].maxx %= k, tree[p].sum %= k; return ;
}
if(nl <= mid) upmod(nl, nr, ls, k);
if(nr > mid) upmod(nl, nr, rs, k);
up(p);
}
void update(int pos, int p, LL k) {
int l = tree[p].l, r = tree[p].r;
if(l == r) {
tree[p].maxx = tree[p].sum = k;
return ;
}
if(pos <= mid) update(pos, ls, k);
else update(pos, rs, k);
up(p);
}
LL query(int nl, int nr, int p) {
int l = tree[p].l, r = tree[p].r;
LL ans = 0;
if(nl <= l && nr >= r) return tree[p].sum;
if(nl <= mid) ans += query(nl, nr, ls);
if(mid < nr) ans += query(nl, nr, rs);
return ans;
}
int main() {
n = read(), q = read();
for(int i = 1; i <= n; ++i) a[i] = read();
build(1, n, 1);
while(q--) {
int opt = read();
if(opt == 1) {
int l = read(), r = read();
printf("%lld\n", query(l, r, 1));
}
else if(opt == 2) {
int l = read(), r = read(); LL k = read();
upmod(l, r, 1, k);
}
else {
int k = read(); LL x = read();
update(k, 1, x);
}
}
return 0;
}原文：https://www.cnblogs.com/morslin/p/11855875.html