CPU监控
历史最大值可以让我们想到吉司机，然后发现这里有个就要考虑区间推平和区间加对lazytag的影响。我们要维护6个tag,maxx,hmaxx,ha,a,hc,c。考虑之前的线段树对于区间覆盖和区间加之怎么做的。我们发现如果我们有一个c标记，那么如果我们要下传一个ad标记，那么我们可以让c加上ad。如果我们要下传一个c标记那我们就覆盖c标记。考虑推广到吉司机上。发现有四种情况（视作一开始就有ad标记，且值为0，所以不会有没ad的情况）
重点代码:
void push_up(long long p){
d[p].maxx=max(d[p<<1].maxx,d[p<<1|1].maxx);
d[p].hmaxx=max(d[p<<1].hmaxx,d[p<<1|1].hmaxx);
}
void update(long long ad,long long had,long long c,long long hc,long long p){
if(d[p].c!=-1e16){
d[p].hc=max(d[p].hc,d[p].c+had);
d[p].c+=ad;
}else{
d[p].had=max(d[p].had,d[p].ad+had);
d[p].ad+=ad;
}
d[p].hmaxx=max(d[p].hmaxx,d[p].maxx+had);
d[p].maxx+=ad;
if(c!=-1e16){
if(d[p].c!=-1e16){
d[p].hc=max(d[p].hc,hc);
d[p].c=c;
}else{
d[p].hc=hc;
d[p].c=c;
}
d[p].maxx=c;
d[p].hmaxx=max(d[p].hmaxx,hc);
}
}
void push_down(long long p){
update(d[p].ad,d[p].had,d[p].c,d[p].hc,p<<1);
update(d[p].ad,d[p].had,d[p].c,d[p].hc,p<<1|1);
d[p].c=d[p].hc=-1e16;
d[p].ad=d[p].had=0;
}
void update_ad(long long l,long long r,long long p,long long s,long long t,long long ad){
if(l>=s&&r<=t){
if(d[p].c!=-1e16){
d[p].hc=max(d[p].hc,d[p].c+ad);
d[p].c+=ad;
}else{
d[p].had=max(d[p].had,d[p].ad+ad);
d[p].ad+=ad;
}
d[p].hmaxx=max(d[p].hmaxx,d[p].maxx+ad);
d[p].maxx+=ad;
return;
}
long long mid=(l+r)>>1;
push_down(p);
if(s<=mid) update_ad(l,mid,p<<1,s,t,ad);
if(t>mid) update_ad(mid+1,r,p<<1|1,s,t,ad);
push_up(p);
}
void update_c(long long l,long long r,long long p,long long s,long long t,long long c){
if(l>=s&&r<=t){
if(d[p].c!=-1e16){
d[p].hc=max(d[p].hc,c);
d[p].c=c;
}else{
d[p].hc=c;
d[p].c=c;
}
d[p].maxx=c;
d[p].hmaxx=max(d[p].hmaxx,c);
return;
}
long long mid=(l+r)>>1;
push_down(p);
if(s<=mid) update_c(l,mid,p<<1,s,t,c);
if(t>mid) update_c(mid+1,r,p<<1|1,s,t,c);
push_up(p);
}
线段树 3
没有2的操作上面讲过了，然后考虑区间推平怎么做。我们可以维护一个maxx,se,mx_ad,ad,cnt然后还有普通的sum,hmx_ad,had,hmaxx然后区间推平时如果这个区间只有一种数大于推平的数，那么就操作，否则就递归下去。因为这个只有ad标记，上面都讲过了
void push_up(long long p){//好理解
d[p].sum=d[p<<1].sum+d[p<<1|1].sum;
d[p].maxx=max(d[p<<1].maxx,d[p<<1|1].maxx);
d[p].hmaxx=max(d[p<<1].hmaxx,d[p<<1|1].hmaxx);
if(d[p<<1].maxx==d[p<<1|1].maxx){
d[p].se=max(d[p<<1].se,d[p<<1|1].se);
d[p].cnt=d[p<<1].cnt+d[p<<1|1].cnt;
}else if(d[p<<1].maxx>d[p<<1|1].maxx){
d[p].se=max(d[p<<1|1].maxx,d[p<<1].se);
d[p].cnt=d[p<<1].cnt;
}else if(d[p<<1].maxx<d[p<<1|1].maxx){
d[p].se=max(d[p<<1].maxx,d[p<<1|1].se);
d[p].cnt=d[p<<1|1].cnt;
}
}
void update(long long mx_ad,long long mx_had,long long ad,long long had,long long p){//顺序,se的id(好理解)
d[p].sum+=(ad*(d[p].r-d[p].l+1-d[p].cnt)+mx_ad*d[p].cnt);
d[p].hmaxx=max(d[p].maxx+mx_had,d[p].hmaxx);
d[p].maxx+=mx_ad;
if(d[p].se!=1e16) d[p].se+=ad;
d[p].mx_had=max(d[p].mx_had,mx_had+d[p].mx_ad);
d[p].had=max(d[p].had,had+d[p].ad);
d[p].ad+=ad;
d[p].mx_ad+=mx_ad;
}
void push_down(long long p){
int maxx=max(d[p<<1].maxx,d[p<<1|1].maxx);//这里要临时存一下,不然会变
if(maxx==d[p<<1].maxx) update(d[p].mx_ad,d[p].mx_had,d[p].ad,d[p].had,p<<1);//下传的是对应的la，是maxx传maxx,否则传次大值的
else update(d[p].ad,d[p].had,d[p].ad,d[p].had,p<<1);
if(maxx==d[p<<1|1].maxx) update(d[p].mx_ad,d[p].mx_had,d[p].ad,d[p].had,p<<1|1);
else update(d[p].ad,d[p].had,d[p].ad,d[p].had,p<<1|1);
d[p].mx_had=d[p].mx_ad=d[p].had=d[p].ad=0;
}
void update_ad(long long l,long long r,long long p,long long s,long long t,long long ad){
if(l>=s&&r<=t){
d[p].sum+=ad*(d[p].r-d[p].l+1);
d[p].hmaxx=max(d[p].maxx+ad,d[p].hmaxx);
d[p].maxx+=ad;
if(d[p].se!=1e16) d[p].se+=ad;
d[p].mx_had=max(d[p].mx_had,d[p].mx_ad+ad);
d[p].had=max(d[p].had,d[p].ad+ad);
d[p].ad+=ad;
d[p].mx_ad+=ad;
return;
}
long long mid=(l+r)>>1;
push_down(p);
if(s<=mid) update_ad(l,mid,p<<1,s,t,ad);
if(t>mid) update_ad(mid+1,r,p<<1|1,s,t,ad);
push_up(p);
}
void update_min(long long l,long long r,long long p,long long s,long long t,long long ad){
if(ad>=d[p].maxx) return;
if(l>=s&&r<=t&&ad>d[p].se){
d[p].sum-=d[p].cnt*(d[p].maxx-ad);
d[p].mx_ad-=(d[p].maxx-ad);
d[p].maxx=ad;
return;
}
long long mid=(l+r)>>1;
push_down(p);
if(s<=mid) update_min(l,mid,p<<1,s,t,ad);
if(t>mid) update_min(mid+1,r,p<<1|1,s,t,ad);
push_up(p);
}