社区讨论

人麻了,自己封装的板子怎么不对呢

P3372【模板】线段树 1参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mhjrbvo3
此快照首次捕获于
2025/11/04 07:14
4 个月前
此快照最后确认于
2025/11/04 07:14
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define int long long 
using namespace std;

template<class Info>
struct SGT{
    int n;
    vector<int>tag;
    vector<Info>info;

    SGT (vector<Info>&init){
        n=init.size();
        info.assign(n*4,Info());
        tag.assign(n*4,0);
        function<void(int,int,int)>build=[&](int p,int l,int r){
            info[p]={l,r,0};
            if(l==r){
                info[p]=init[l];
                return;
            }
            int mid=l+r>>1;
            build(2*p,l,mid);
            build(2*p+1,mid+1,r);
            pull(p);
        };
        build(1,1,n);
    }    

    void pull(int p){
        info[p]=info[2*p]+info[2*p+1];
    }

    void add(int p,int v){
        tag[p]+=v;
        info[p].sum+=(info[p].r-info[p].l+1)*v;
    }

    void push(int p){
        add(2*p,tag[p]);
        add(2*p+1,tag[p]);
        tag[p]=0;
    }

    Info query(int p,int nowl,int nowr,int l,int r){
        if(nowl>r||nowr<l){
            return {};
        }
        if(nowl>=l&&nowr<=r){
            return info[p];
        }
        push(p);
        int mid=(nowl+nowr)/2;
        return query(2*p,nowl,mid,l,r)+query(2*p+1,mid+1,nowr,l,r);
    }

    Info query(int l,int r){
        return query(1,1,n,l,r);
    }

    void rangeadd(int p,int nowl,int nowr,int l,int r,int v){
        if(nowl>r||nowr<l){
            return;
        }
        if(nowl>=l&&nowr<=r){
            add(p,v);
            return;
        }
        int mid=nowl+nowr>>1;
        push(p);
        rangeadd(2*p,nowl,mid,l,r,v);
        rangeadd(2*p+1,mid+1,nowr,l,r,v);
        pull(p);
    }
    void rangeadd(int l,int r,int v){
        rangeadd(1,1,n,l,r,v);
    }
};

struct Info{
    int l,r;
    int sum=0;
};

Info operator+(const Info&a,const Info&b){
    Info tem;
    tem.sum=a.sum+b.sum;
    return tem;
}

void solve(){
    int n,q;cin>>n>>q;
    vector<Info>a(n+1);
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        a[i]={i,i,x};
    }
    SGT<Info>sgt(a);
    while(q--){
        int op;cin>>op;
        if(op==1){
            int l,r,v;cin>>l>>r>>v;
            sgt.rangeadd(l,r,v);
        }else{
            int l,r;cin>>l>>r;
            cout<<sgt.query(l,r).sum<<"\n";
        }
    }
}
                   
signed main(){
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int T=1; 
   //cin>>T;
   while(T--){
      solve();
   }
   return 0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...