Cf438D The Child and Sequence

有点吉司机线段树的味

#include<bits/stdc++.h>

using namespace std;

using ll=long long;


const int maxn=1e5+9;
struct Node{
    ll l,r,v,ma;
}tr[maxn<<2];

ll n,m,a[maxn];

void build (int l,int r,int tot){
    if(l==r){
        tr[tot].v=tr[tot].ma=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,tot<<1),build(mid+1,r,(tot<<1)|1);
    tr[tot].v=tr[tot<<1].v+tr[(tot<<1)|1].v,tr[tot].ma=max(tr[tot<<1].ma,tr[(tot<<1)|1].ma);
}

void modify(int x,int l,int r,int tot){
    if(l==r){
        tr[tot].v=tr[tot].ma=a[l];
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)modify(x,l,mid,tot<<1);
    else modify(x,mid+1,r,(tot<<1)|1);
    tr[tot].v=tr[tot<<1].v+tr[(tot<<1)|1].v,tr[tot].ma=max(tr[tot<<1].ma,tr[(tot<<1)|1].ma);
}

void getmod(int nl,int nr,int tot,int l,int r,int mod){
    if(nl==nr){
        tr[tot].v=tr[tot].ma=a[nl]=a[nl]%mod;
        return;
    }
    if(tr[tot].ma<mod)return;
    int mid=(nl+nr)>>1;
    if(mid>=l)getmod(nl,mid,tot<<1,l,r,mod);
    if(mid<r)getmod(mid+1,nr,(tot<<1)|1,l,r,mod);
    tr[tot].v=tr[tot<<1].v+tr[(tot<<1)|1].v,tr[tot].ma=max(tr[tot<<1].ma,tr[(tot<<1)|1].ma);
}

ll getsum(int nl,int nr,int tot,int l,int r){
    if(nl>=l&&nr<=r)return tr[tot].v;
    ll mid=(nl+nr)>>1,res=0;
    if(mid>=l)res+=getsum(nl,mid,tot<<1,l,r);
    if(mid<r)res+=getsum(mid+1,nr,(tot<<1)|1,l,r);
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
        build(1,n,1);
    for(int i=1,x,y,z,w;i<=m;++i){
        cin>>x>>y>>z;
        if(x==1){
            cout<<getsum(1,n,1,y,z)<<"\n";
        }else if(x==2){
            cin>>w;
            getmod(1,n,1,y,z,w);
        }else {
            a[y]=z;
            modify(y,1,n,1);
        }
    }
}