Day4

今天讲线段树，由于之前我已经介绍过了，这里直接贴代码

void pushup(int p){
    tree[p]=tree[p<<1]+tree[p<<1|1];
}
void pushdown(int p,int l,int r){
    int d=tag[p];
    int mid=(l+r)>>1;
    tree[p<<1]+=d*(mid-l+1);
    tree[p<<1|1]+=d*(r-mid);
    tag[p<<1]+=d;
    tag[p<<1|1]+=d;
    tag[p]=0;
}
void undate(int l,int r,int d,int p,int pl,int pr){
    if(pl>=l&&pr<=r){
        tree[p]+=d*(pr-pl+1);
        tag[p]+=d;
        return;
    }
    if(tag[p])pushdown(p,pl,pr);
    int mid=(pl+pr)>>1;
    if(l<=mid)undate(l,r,d,p<<1,pl,mid);
    if(r>=mid+1)undate(l,r,d,p<<1|1,mid+1,pr);
    pushup(p);
}
int query(int l,int r,int p,int pl,int pr){
    if(l<=pl&&pr<=r){
        return tree[p];
    }
    pushdown(p,pl,pr);
    int mid=(pl+pr)>>1;
    int ret=0;
    if(l<=mid)ret+=query(l,r,p<<1,pl,mid);
    if(r>=mid+1)ret+=query(l,r,p<<1|1,mid+1,pr);
    return ret;
}