劳请dalao调线段树!?

P3372 【模板】线段树 1

ILoveSoviet @ 2023-07-12 22:42:49

#include<iostream>
using namespace std;
int n,dat[100005];
struct node{
    int l,r,dat,lazy;
}tree[100005];
inline int ll(int i){return i*2;}
inline int rr(int i){return i*2+1;}
inline void nex(int d){
    if(tree[d].l==tree[d].r){
        tree[d].dat+=tree[d].lazy;
        tree[d].lazy=0;
        return;
    }
    tree[d].dat+=tree[d].lazy*(tree[d].r-tree[d].l+1);
    tree[ll(d)].lazy+=tree[d].lazy;
    tree[rr(d)].lazy+=tree[d].lazy;
    tree[d].lazy=0;
}
void make_tree(int d,int l,int r){
    tree[d].l=l;
    tree[d].r=r;
    if(l==r){
        tree[d].dat=dat[l];
    }
    else{
        int mid=(l+r)/2;
        make_tree(ll(d),l,mid);
        make_tree(rr(d),mid+1,r);
        tree[d].dat=tree[ll(d)].dat+tree[rr(d)].dat;
    }
}
int find_a_dat(int i,int d){
    nex(d);
    // cout<<d<<" ";
    int l=tree[d].l,r=tree[d].r;
    if(l==r&&r==i){
        return tree[d].dat;
    }
    int mid=(l+r)/2;
    if(i<=mid)  return find_a_dat(i,ll(d));
    else if(i>mid)   return find_a_dat(i,rr(d));
}
void add_a_dat(int i,int d,int add){
    nex(d);
    // cout<<i<<" ";
    int l=tree[d].l,r=tree[d].r;
    if(l==r){
        tree[d].dat+=add;
        return;
    }
    int mid=(l+r)/2;
    if(i<=mid)  add_a_dat(i,ll(d),add);
    else if(i>mid)   add_a_dat(i,rr(d),add);
    tree[d].dat=tree[ll(d)].dat+tree[rr(d)].dat;
}
int find_a_line(int d,int l,int r){
    nex(d);
    int l1=tree[d].l,r1=tree[d].r;
    if(l1==l&&r1==r)    return tree[d].dat;
    int mid=(l1+r1)/2;
    if(mid<l)   return find_a_line(rr(d),l,r);
    else if(mid>=r) return find_a_line(ll(d),l,r);
    else return find_a_line(ll(d),l,mid)+find_a_line(rr(d),mid+1,r);
}
void add_a_line(int d,int l,int r,int add){
    nex(d);
    int l1=tree[d].l,r1=tree[d].r;
    if(l1==l&&r1==r){
        tree[d].lazy+=add;
        nex(d);
        return;
    }
    int mid=(l1+r1)/2;
    if(mid<l)   add_a_line(rr(d),l,r,add);
    else if(mid>=r)  add_a_line(ll(d),l,r,add);
    else        add_a_line(ll(d),l,mid,add),add_a_line(rr(d),mid+1,r,add);
    tree[d].dat=tree[ll(d)].dat+tree[rr(d)].dat;
}
int main(){
    int n;
    cin>>n;
    int p;
    cin>>p;
    for(int i=1;i<=n;i++){
        cin>>dat[i];
    }
    make_tree(1,1,n);
    while(p--){
        int op;
        cin>>op;
        // if(op==0){
        //     int v;
        //     cin>>v;
        //     cout<<find_a_dat(v,1);
        // }
        // else if(op==1){
        //     int v,add;
        //     cin>>v>>add;
        //     add_a_dat(v,1,add);
        // }
        if(op==2){
            int l,r;
            cin>>l>>r;
            cout<<find_a_line(1,l,r)<<endl;
        }
        else if(op==1){
            int l,r,add;
            cin>>l>>r>>add;
            add_a_line(1,l,r,add);
        }
    }
}

万分感谢!


by OldDriverTree @ 2023-07-12 22:51:59

@ILoveSoviet 没 pushdown 呀


by suzhikz @ 2023-07-12 22:55:22

@OldDriverTree 头像真好看


by WsW_ @ 2023-07-12 23:06:02

?这是动态开点吗?


|