求问,线段树RE
查看原帖
求问,线段树RE
338786
mushroom_knight楼主2021/2/13 22:38

RT,我省去了快读部分。

不知道哪里出了问题/kk

求带师帮忙看看/qq

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int si=4e5+10;
int n,m;
int a[si];
struct segment_tree{
    int l,r;//dat interval
    int value,lazy;
    #define l(o) t[o].l
    #define r(o) t[o].r
    #define sum(o) t[o].value
    #define tag(o) t[o].lazy
    #define lson(o) o<<1
    #define rson(o) o<<1|1
}t[si*4];

inline void pushdown(int p){
    if(tag(p)){
        sum(lson(p))+=tag(p)*(r(lson(p))-l(lson(p))+1);
        sum(rson(p))+=tag(p)*(r(rson(p))-l(rson(p))+1);//update information
        tag(lson(p))+=tag(p),tag(rson(p))+=tag(p);//spread tag 
        tag(p)=0;//delete
    }return;
}

inline void build(int p,int l,int r){
    int nl=l(p),nr=r(p);
    if(nl==nr){
        sum(p)=a[nl];//or a[nr];//value of leaf
        return;
    }
    int mid=(nl+nr)>>1;
    build(lson(p),nl,mid);
    build(rson(p),mid+1,nr);
    sum(p)=sum(lson(p))+sum(rson(p));//Update(or minv,maxv,sin,cos……)
}

inline void modify(int p,int x,int val){
    int l=l(p),r=r(p);
    if(l==r){//find leaf
        sum(p)=val;return;
    }
    int mid=(l+r)>>1;
    if(x<=mid){//in leftson
        modify(lson(p),x,val);
    }
    else{//in rightson
        modify(rson(p),x,val);
    }
    sum(p)=sum(lson(p))+sum(rson(p));//Update
}

inline int query(int p,int l,int r){
	int res=0,nl=l(p),nr=r(p); 
    if(l<=nl&&nr<=r){
        return sum(p);
	}
    pushdown(p);
    int mid=(nl+nr)>>1;
    if(l<=mid){
        res+=query(lson(p),nl,mid);
	}
    if(r>mid){
        res+=query(rson(p),mid+1,nr);
	}
    return res;
}

inline void update(int p,int l,int r,int v){
    int nl=l(p),nr=r(p);
    if(l<=nl&&nr<=r){
        sum(p)+=v*(nr-nl+1);
        tag(p)+=v;
        return;
    }
    pushdown(p);
    int mid=(nl+nr)>>1;
    if(l<=mid){
        update(lson(p),l,r,v);
    }
    if(r>mid){
        update(rson(p),l,r,v);
    }
    sum(p)=sum(lson(p))+sum(rson(p));
}

signed main(){
    read(n),read(m);
    readrange(a,1,n);
    build(1,1,n);
    while(m--){
        int op,x,y,k;
        read(op),read(x),read(y);
        if(op==1){
            read(k);
            update(1,x,y,k);
        }else{
            write(query(1,x,y))ent;
        }
    }
    return 0;
}

2021/2/13 22:38
加载中...