吉司机线段树

hdu5306

#define ml ((l+r)>>1)
#define mr (ml+1)
#define ls (rt<<1)
#define rs (ls|1)
int mx1[maxn<<2],num[maxn<<2],mx2[maxn<<2],lz[maxn<<2],a[maxn];
long long sum[maxn<<2];

void push_son(int son,int l,int r,int lzrt){//把最大值变为lzrt ，次大值不变
    if(lzrt<mx1[son]){
        sum[son]-=1ll*(mx1[son]-lzrt)*num[son];
        mx1[son]=lzrt;
        lz[son]=lzrt;
    }
}

void push_down(int rt,int l,int r){
    push_son(ls,l,ml,lz[rt]);
    push_son(rs,mr,r,lz[rt]);
    lz[rt]=0x7fffffff;
}

void push_up(int rt,int l,int r){
    if(mx1[ls]==mx1[rs]){
        mx1[rt]=mx1[ls];
        num[rt]=num[ls]+num[rs];
        mx2[rt]=max(mx2[ls],mx2[rs]);
    }
    else{
        if(mx1[ls]>mx1[rs]){
            mx1[rt]=mx1[ls];
            num[rt]=num[ls];
            mx2[rt]=max(mx2[ls],mx1[rs]);
        }
        else{
            mx1[rt]=mx1[rs];
            num[rt]=num[rs];
            mx2[rt]=max(mx2[rs],mx1[ls]);
        }
    }
    sum[rt]=sum[ls]+sum[rs];
}

void build(int rt,int l,int r){
    lz[rt]=0x7fffffff;
    if(l==r){
        mx1[rt]=a[l];
        num[rt]=1;
        mx2[rt]=-1;// none 
        sum[rt]=a[l];
    }
    else{
        build(ls,l,ml);
        build(rs,mr,r);
        push_up(rt,l,r);
    }
}

void update(int rt,int l,int r,int ql,int qr,int val){
    if(mx1[rt]<=val) return ;//无影响
    if(ql<=l&&r<=qr&&mx2[rt]<val){//只影响最大值，不影响次大值
        push_son(rt,l,r,val);
    }
    else{
        push_down(rt,l,r);
        if(ml>=ql)update(ls,l,ml,ql,qr,val);
        if(mr<=qr)update(rs,mr,r,ql,qr,val);
        push_up(rt,l,r);
    }
}

long long query_sum(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return sum[rt];
    }
    else{
        push_down(rt,l,r);
        long long ret=0;
        if(ml>=ql) ret+=query_sum(ls,l,ml,ql,qr);
        if(mr<=qr) ret+=query_sum(rs,mr,r,ql,qr);
        return ret;
    }
}

int query_max(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return mx1[rt];
    }
    else{
        push_down(rt,l,r);
        int ret=0;
        if(ml>=ql) ret=max(ret,query_max(ls,l,ml,ql,qr));
        if(mr<=qr) ret=max(ret,query_max(rs,mr,r,ql,qr));
        return ret;
    }
}