The Child and Sequence （线段树取模）

浅浅的花香味﹌ 2023-06-03 13:00 18阅读 0赞

题意：线段树取模操作，维护两个数组，一个维护当前区间的最大值，一个维护当前区间的和，如果最大值小于mod，就不用再往下取模了；单点更新，区间查找正常操作~；；；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    using namespace std;
    const int maxn=1e5+10;
    const int inf=0x3f3f3f3f;
    typedef long long ll;
    ll a[maxn],tree[maxn*4],lazy[maxn*4];
    ll maxtree[maxn*4];
    void build(int l,int r,int now){
        if(l==r){
            tree[now]=maxtree[now]=a[l];
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,now<<1);
        build(mid+1,r,now<<1|1);
        tree[now]=tree[now<<1]+tree[now<<1|1];
        maxtree[now]=max(maxtree[now<<1],maxtree[now<<1|1]);
    }
    void o3(int l,int r,int now,int k,ll s){
        if(l==r){
            tree[now]=s;
            maxtree[now]=s;
            return;
        }
        int mid=(l+r)>>1;
        if(mid>=k)o3(l,mid,now<<1,k,s);
        else o3(mid+1,r,now<<1|1,k,s);
        tree[now]=tree[now<<1]+tree[now<<1|1];
        maxtree[now]=max(maxtree[now<<1],maxtree[now<<1|1]);
    }
    void o2(int l,int r,int now,int L,int R,int s){
        if(s>maxtree[now])return;
        if(l==r){
            tree[now]%=s;
            maxtree[now]%=s;
            return;
        }
        int mid=(l+r)>>1;
        if(mid>=L)o2(l,mid,now<<1,L,R,s);
        if(mid<R)o2(mid+1,r,now<<1|1,L,R,s);
        tree[now]=tree[now<<1]+tree[now<<1|1];
        maxtree[now]=max(maxtree[now<<1],maxtree[now<<1|1]);
    }
    ll o1(int l,int r,int now,int L,int R){
        if(l>=L&&r<=R){
            return tree[now];
        }
        int mid=(l+r)>>1;
        ll sum=0;
        if(L<=mid)sum+=o1(l,mid,now<<1,L,R);
        if(R>mid)sum+=o1(mid+1,r,now<<1|1,L,R);
        return sum;
    }
    int main(){
        ios::sync_with_stdio(false);
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)cin>>a[i];
        build(1,n,1);
        while(m--){
            int op,x,y;ll c;
            cin>>op;
            if(op==1){
                cin>>x>>y;
                cout<<o1(1,n,1,x,y)<<endl;
            }
            else if(op==2){
                cin>>x>>y>>c;
                o2(1,n,1,x,y,c);
            }
            else {
                cin>>x>>c;
                o3(1,n,1,x,c);
            }
        }
    
    
    
        return 0;
    }

转载于:https://www.cnblogs.com/lin1874/p/11286643.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/e3a4c7717c244c3ca436fa8cc42d5126.png