线段树维护区间取模，单点修改，区间求和。
这题老套路了，对一个数来说，每次取模至少让它减少一半，这样每次单点修改对时间复杂度的贡献就是一个log” role=”presentation” style=”position: relative;”>loglog，所以维护区间最大值剪枝，然后每次单点暴力取模，这样的话时间复杂度为O（nlogn）” role=”presentation” style=”position: relative;”>O（nlogn）O（nlogn）。
代码如下：
#include<bits/stdc++.h>#define lc (p<<1)#define rc (p<<1|1)#define mid (T[p].l+T[p].r>>1)#define N 100005#define ll long longusing namespace std;inline ll read(){ ll ans=0; char ch=getchar(); while(!isdigit(ch))ch=getchar(); while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar(); return ans;}inline void write(ll x){ if(x>9)write(x/10); putchar((x%10)^48);}ll n,m,a[N];struct Node{ll l,r,sum,maxn;}T[N<<2];inline ll max(ll a,ll b){return a>b?a:b;}inline void pushup(ll p){T[p].sum=T[lc].sum+T[rc].sum,T[p].maxn=max(T[lc].maxn,T[rc].maxn);}inline void build(ll p,ll l,ll r){ T[p].l=l,T[p].r=r; if(l==r){T[p].sum=T[p].maxn=a[l];return;} build(lc,l,mid),build(rc,mid+1,r),pushup(p);}inline void update(ll p,ll k,ll v){ if(T[p].l==T[p].r){T[p].maxn=T[p].sum=v;return;} if(k<=mid)update(lc,k,v); else update(rc,k,v); pushup(p);}inline void modify(ll p,ll ql,ll qr,ll v){ if(ql>T[p].r||qr<T[p].l||v>T[p].maxn)return; if(T[p].l==T[p].r){T[p].sum=T[p].maxn=T[p].sum%v;return;} if(qr<=mid)modify(lc,ql,qr,v); else if(ql>mid)modify(rc,ql,qr,v); else modify(lc,ql,mid,v),modify(rc,mid+1,qr,v); pushup(p);}inline ll query(ll p,ll ql,ll qr){ if(ql>T[p].r||qr<T[p].l)return 0; if(ql<=T[p].l&&T[p].r<=qr)return T[p].sum; if(qr<=mid)return query(lc,ql,qr); if(ql>mid)return query(rc,ql,qr); return query(lc,ql,mid)+query(rc,mid+1,qr);}int main(){ n=read(),m=read(); for(ll i=1;i<=n;++i)a[i]=read(); build(1,1,n); while(m--){ ll op=read(),a=read(),b=read(); switch(op){ case 1:{write(query(1,a,b)),puts("");break;} case 2:{ll v=read();modify(1,a,b,v);break;} default:{update(1,a,b);break;} } } return 0;}
