存档【线段树】

本是古典何须时尚 2024-03-17 17:32 69阅读 0赞

存一下写到一般的线段树

呃呃

[1008-数据结构\_2021秋季算法入门班第十一章习题：线段树、树状数组 (nowcoder.com)][1008-_2021_ _nowcoder.com]

#include <bits/stdc++.h>
     
    #define int long long
     
    using namespace std;
     
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    const int Inf=1e18;
    
    struct info{
        int sum;
    };
    
    info operator+(const info &l,const info &r){
        info res;
        res.sum=l.sum+r.sum;
        return res;
    }
    
    struct tag{
        int add,mul;
    };
    
    struct Segtree{
        info val;
        tag t;
    }tree[mxe<<2][3];
    //1为区间和,2为区间平方和
    
    int N,M,op,l,r,x;
    int a[mxn];
    
    void pushup(int rt){
        tree[rt][1].val=tree[rt<<1][1].val+tree[rt<<1|1][1].val;
        tree[rt][2].val=tree[rt<<1][2].val+tree[rt<<1|1][2].val;
    }
    void settag1(int rt,int tot){
    
    }
    void settag2(int rt,int tot){
    
    }
    void pushdown(int rt,int tot){
        for(int i=1;i<=2;i++){
            if(tree[rt][i].t.add!=0||tree[rt][i].t.mul!=1){
                if(i==1){
                    settag1(rt<<1,tot-tot/2);
                    settag1(rt<<1|1,tot/2);
                }else{
                    settag2(rt<<1,tot-tot/2);
                    settag2(rt<<1|1,tot/2);
                }
                tree[rt][i].t.add=0;
                tree[rt][i].t.mul=1;
                return;
            }
        }
    }
    void build(int rt,int l,int r){
        if(l==r){
            //tag
            tree[rt][1].t.add=tree[rt][2].t.add=0;
            tree[rt][1].t.mul=tree[rt][2].t.mul=1;
            //val
            tree[rt][1].val.sum=a[l];
            tree[rt][2].val.sum=a[l]*a[l];
            return;
        }
        int mid=l+r>>1;
        build(rt<<1,l,mid);
        build(rt<<1|1,mid+1,r);
        pushup(rt);
    }
    void modify(int rt,int l,int r,int x,int y,int k,int mode){
        if(x<=l&&r<=y){
            if(mode==1){
                //区间加
                settag1(rt,r-l+1);
                //1
                tree[rt][1].val.sum+=k*(r-l+1);
                //2
                tree[rt][2].val.sum=tree[rt][2].val.sum+2*k*tree[rt][1].val.sum+(r-l+1)*k*k;
            }else{
                //区间乘
                settag2(rt,r-l+1);
                //1
                tree[rt][1].val.sum*=k;
                //2
                tree[rt][2].val.sum*=k*k;
            }
            return;
        }
        pushdown(rt,r-l+1);
        int mid=l+r>>1;
        if(x<=mid) modify(rt<<1,l,mid,x,y,k,mode);
        if(y>mid) modify(rt<<1|1,mid+1,r,x,y,k,mode);
        pushup(rt);
    }
    info query(int rt,int l,int r,int x,int y,int mode){
        if(x<=l&&r<=y){
            if(mode==1){
                return tree[rt][1].val;
            }else{
                return tree[rt][2].val;
            }
        }
        pushdown(rt,r-l+1);
        int mid=l+r>>1;
        if(x>mid) return query(rt<<1|1,mid+1,y,x,y,mode);
        else if(y<=mid) return query(rt<<1,l,mid,x,y,mode);
        else{
            return query(rt<<1,l,mid,x,y,mode)+query(rt<<1|1,mid+1,r,x,y,mode);
        }
    }
    void solve(){
        cin>>N>>M;
        for(int i=1;i<=N;i++) cin>>a[i];
        build(1,1,N);
        while(M--){
            cin>>op;
            if(op==1){
                cin>>l>>r;
                cout<<query(1,1,N,l,r,1).sum<<'\n';
            }else if(op==2){
                cin>>l>>r;
                cout<<query(1,1,N,l,r,2).sum<<'\n';
            }else if(op==3){
                cin>>l>>r>>x;
                modify(1,1,N,l,r,x,2);
            }else{
                cin>>l>>r>>x;
                modify(1,1,N,l,r,x,1);
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[1008-_2021_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/26896/1008