题目链接：https://codeforces.com/problemset/problem/438/D
题目大意：给你n个数，有三种操作，一是对区间$[l,r]$求和，二是对区间$[l,r]$中每个数对$x$取模，三是单点修改。
Examples
5 5
1 2 3 4 5
2 3 5 4
3 3 5
1 2 5
2 1 3 3
1 1 3
8
5
10 10
6 9 6 7 6 1 10 10 9 5
1 3 9
2 7 10 9
2 5 10 8
1 4 7
3 3 7
2 7 9 9
1 2 4
1 6 6
1 5 9
3 1 10
49
15
23
1
9
emmmm，一和三没什么好说的，就是第二个操作可能有点小问题，最为暴力的写法就是每个点都取模，不过这样的话就很费时间，会T掉，那么我们要去优化，想到之前我们写过的吉司机线段树，维护最大值和次大值，那么我们也可以这么想，如果取模的数大于最大值就直接return了，然后对于次大值的时候单独讨论，其他的全部更新到根节点。只不过本题的次大值维护有点麻烦。。。所以尝试一波只维护最大值，交一发。。。A了！！！
以下是AC代码：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define lc rt<<1 #define rc rt<<1|1 typedef long long ll; const int mac=1e5+10; const int inf=1e9+10; ll sum[mac<<2]; int mx[mac<<2]; void update_range(int l,int r,int rt,int L,int R,int mod) { if (mod>mx[rt]) return; if (l==r) { sum[rt]=mx[rt]=mx[rt]%mod; return; } int mid=(l+r)>>1; if (mid>=L) update_range(lson,L,R,mod); if (mid<R) update_range(rson,L,R,mod); sum[rt]=sum[lc]+sum[rc]; mx[rt]=max(mx[lc],mx[rc]); } void update_point(int l,int r,int rt,int pos,int x) { if (l==r) {sum[rt]=x; mx[rt]=x; return;} int mid=(l+r)>>1; if (mid>=pos) update_point(lson,pos,x); else update_point(rson,pos,x); sum[rt]=sum[lc]+sum[rc]; mx[rt]=max(mx[lc],mx[rc]); } ll query(int l,int r,int rt,int L,int R) { ll ans=0; if (l>=L && r<=R) return sum[rt]; int mid=(l+r)>>1; if (mid>=L) ans+=query(lson,L,R); if (mid<R) ans+=query(rson,L,R); return ans; } void build(int l,int r,int rt) { if (l==r){ int x; scanf ("%d",&x); mx[rt]=sum[rt]=x; return; } int mid=(l+r)>>1; build(lson);build(rson); sum[rt]=sum[lc]+sum[rc]; mx[rt]=max(mx[lc],mx[rc]); } int main() { //freopen("in.txt","r",stdin); int n,q; scanf ("%d%d",&n,&q); build(1,n,1); while (q--){ int opt,l,r,x,pos; scanf ("%d",&opt); if (opt==1){ scanf ("%d%d",&l,&r); printf("%lld\n",query(1,n,1,l,r)); } else if (opt==2){ scanf ("%d%d%d",&l,&r,&x); update_range(1,n,1,l,r,x); } else { scanf ("%d%d",&pos,&x); update_point(1,n,1,pos,x); } } return 0; }
CodeForces - 438D--The Child and Sequence（区间取模线段树）
原文：https://www.cnblogs.com/lonely-wind-/p/13277103.html