吉司机线段树
一、区间历史最值
以区间历史最大值为例。首先，相应地，设 \(maxb\) 表示一个节点的区间历史最大值。为了更新一个区间的子区间，再设一个 \(tag2\) ，表示 \(tag1\) 从上次 \(push\_down\) 以后到现在达到过的最大值。
\(code:\)
void push_up(int u){
p[u].w=p[u<<1].w+p[u<<1|1].w;
p[u].maxa=max(p[u<<1].maxa,p[u<<1|1].maxa);
p[u].maxb=max(p[u<<1].maxb,p[u<<1|1].maxb);
}
void push_down(int u){//push_down时，注意先下传maxb,tag2，后下传maxa,tag1
p[u<<1].w+=(p[u<<1].r-p[u<<1].l+1)*p[u].tag1;
p[u<<1|1].w+=(p[u<<1|1].r-p[u<<1|1].l+1)*p[u].tag1;
p[u<<1].maxb=max(p[u<<1].maxb,p[u<<1].maxa+p[u].tag2);
p[u<<1|1].maxb=max(p[u<<1|1].maxb,p[u<<1|1].maxa+p[u].tag2);
p[u<<1].tag2=max(p[u<<1].tag2,p[u<<1].tag1+p[u].tag2);
p[u<<1|1].tag2=max(p[u<<1|1].tag2,p[u<<1|1].tag1+p[u].tag2);
p[u<<1].maxa+=p[u].tag1;
p[u<<1|1].maxa+=p[u].tag1;
p[u<<1].tag1+=p[u].tag1;
p[u<<1|1].tag1+=p[u].tag1;
p[u].tag1=p[u].tag2=0;
}
void build(int u,int l,int r){
p[u].l=l;p[u].r=r;
if(l==r){
p[u].w=p[u].maxa=p[u].maxb=a[l];
return ;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);build(u<<1|1,mid+1,r);
push_up(u);
}
void add(int u,int l,int r,int w){
if(p[u].l>=l&&p[u].r<=r){
p[u].w+=(p[u].r-p[u].l+1)*w;
p[u].tag1+=w;
p[u].maxa+=w;
p[u].tag2=max(p[u].tag2,p[u].tag1);
p[u].maxb=max(p[u].maxb,p[u].maxa);
return ;
}
push_down(u);
int mid=(p[u].l+p[u].r)>>1;
if(mid>=l)
add(u<<1,l,r,w);
if(mid<r)
add(u<<1|1,l,r,w);
push_up(u);
}
int ask(int u,int l,int r,int opt){
if(p[u].l>=l&&p[u].r<=r){
if(opt==1) return p[u].w;
else if(opt==2) return p[u].maxa;
else return p[u].maxb;
}
push_down(u);
int re=0,maxx=-1e18,mid=(p[u].l+p[u].r)>>1;
if(mid>=l){
if(opt==1) re+=ask(u<<1,l,r,opt);
else maxx=max(maxx,ask(u<<1,l,r,opt));
}
if(mid<r){
if(opt==1) re+=ask(u<<1|1,l,r,opt);
else maxx=max(maxx,ask(u<<1|1,l,r,opt));
}
if(opt==1) return re;
else return maxx;
}
区间最值操作
以区间最小值操作，即把区间的所有数变成 \(min(w,a[i])\) 为例。设 \(max2\) 表示一个区间的严格次大值（不等于最大值）， \(cnt\) 表示一个区间的最大值的个数。在进行区间最值操作时时，设给定的数为 \(w\) ，那么只有当 \(max2<w<maxa\) 时，才对当前区间更新。
此外，可以发现，该操作会导致区间最大值的 \(tag\) 和其他值的 \(tag\) 不一样。此时需要设四个 \(tag\) 。
设 \(tag1\) 表示区间最大值的 \(tag\) ， \(tag2\) 表示区间次大值的 \(tag\) ； \(tag3\) 表示 \(tag1\) 从上次 \(push\_down\) 以后达到过的最大值； \(tag4\) 表示 \(tag2\) 从上次 \(push\_down\) 以后达到过的最大值。
\(code:\)
void push_up(int u){
p[u].w=p[u<<1].w+p[u<<1|1].w;
p[u].maxa=max(p[u<<1].maxa,p[u<<1|1].maxa);
p[u].maxb=max(p[u<<1].maxb,p[u<<1|1].maxb);
if(p[u<<1].maxa==p[u<<1|1].maxa){
p[u].max2=max(p[u<<1].max2,p[u<<1|1].max2);
p[u].cnt=p[u<<1].cnt+p[u<<1|1].cnt;
}
else if(p[u<<1].maxa>p[u<<1|1].maxa){
p[u].max2=max(p[u<<1].max2,p[u<<1|1].maxa);
p[u].cnt=p[u<<1].cnt;
}
else{
p[u].max2=max(p[u<<1|1].max2,p[u<<1].maxa);
p[u].cnt=p[u<<1|1].cnt;
}
}
void change(int k1,int k2,int k3,int k4,int u){
p[u].w+=k1*p[u].cnt+k2*(p[u].r-p[u].l+1-p[u].cnt);
p[u].maxb=max(p[u].maxb,p[u].maxa+k3);
p[u].maxa+=k1;
if(p[u].max2!=-1e18)
p[u].max2+=k2;
p[u].tag3=max(p[u].tag3,p[u].tag1+k3);
p[u].tag4=max(p[u].tag4,p[u].tag2+k4);
p[u].tag1+=k1;p[u].tag2+=k2;
}
void push_down(int u){//push_down时，注意先下传maxb,tag2，后下传maxa,tag1
int maxx=max(p[u<<1].maxa,p[u<<1|1].maxa);
if(p[u<<1].maxa==maxx)
change(p[u].tag1,p[u].tag2,p[u].tag3,p[u].tag4,u<<1);
else
change(p[u].tag2,p[u].tag2,p[u].tag4,p[u].tag4,u<<1);
if(p[u<<1|1].maxa==maxx)
change(p[u].tag1,p[u].tag2,p[u].tag3,p[u].tag4,u<<1|1);
else
change(p[u].tag2,p[u].tag2,p[u].tag4,p[u].tag4,u<<1|1);
p[u].tag1=p[u].tag2=p[u].tag3=p[u].tag4=0;
}
void build(int u,int l,int r){
p[u].l=l;p[u].r=r;
if(l==r){
p[u].w=p[u].maxa=p[u].maxb=a[l];
p[u].cnt=1;p[u].max2=-1e18;
return ;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);build(u<<1|1,mid+1,r);
push_up(u);
}
void add(int u,int l,int r,int w){
if(p[u].l>=l&&p[u].r<=r){
p[u].w+=(p[u].r-p[u].l+1)*w;
p[u].maxa+=w;
p[u].maxb=max(p[u].maxb,p[u].maxa);
if(p[u].max2!=-1e18)
p[u].max2+=w;
p[u].tag1+=w;p[u].tag2+=w;
p[u].tag3=max(p[u].tag3,p[u].tag1);
p[u].tag4=max(p[u].tag4,p[u].tag2);
return ;
}
push_down(u);
int mid=(p[u].l+p[u].r)>>1;
if(mid>=l)
add(u<<1,l,r,w);
if(mid<r)
add(u<<1|1,l,r,w);
push_up(u);
}
void minn(int u,int l,int r,int w){
if(p[u].maxa<=w)
return ;
if(p[u].l>=l&&p[u].r<=r&&p[u].max2<w){
int k=p[u].maxa-w;
p[u].w-=p[u].cnt*k;
p[u].maxa=w;p[u].tag1-=k;
return ;
}
push_down(u);
int mid=(p[u].l+p[u].r)>>1;
if(mid>=l)
minn(u<<1,l,r,w);
if(mid<r)
minn(u<<1|1,l,r,w);
push_up(u);
}
int ask(int u,int l,int r,int opt){
if(p[u].l>=l&&p[u].r<=r){
if(opt==1) return p[u].w;
else if(opt==2) return p[u].maxa;
else return p[u].maxb;
}
push_down(u);
int re=0,maxx=-1e18,mid=(p[u].l+p[u].r)>>1;
if(mid>=l){
if(opt==1) re+=ask(u<<1,l,r,opt);
else maxx=max(maxx,ask(u<<1,l,r,opt));
}
if(mid<r){
if(opt==1) re+=ask(u<<1|1,l,r,opt);
else maxx=max(maxx,ask(u<<1|1,l,r,opt));
}
if(opt==1) return re;
else return maxx;
}
P4314 CPU 监控
题目要求维护一个支持区间推平，区间加，区间历史最值的线段树。
设 \(tag1\) 表示区间加的 \(tag\) ， \(tag2\) 表示 \(tag1\) 的最大值， \(tag3\) 表示区间推平的 \(tag\) ， \(tag4\) 表示 \(tag3\) 的最大值，然后就可以维护了。情况比较复杂，不要漏掉或写错每一个情况。另外，别忘了把 \(tag4\) 的初始值设为 \(-INF\) 。
\(code:\)
void push_down(int u){
if(p[u].ok){
p[u<<1].maxb=max(p[u<<1].maxb,max(p[u<<1].maxa+p[u].tag2,p[u].tag4));
p[u<<1|1].maxb=max(p[u<<1|1].maxb,max(p[u<<1|1].maxa+p[u].tag2,p[u].tag4));
p[u<<1].maxa=p[u<<1|1].maxa=p[u].tag3;
p[u<<1].tag4=max(p[u<<1].tag4,p[u].tag4);
p[u<<1|1].tag4=max(p[u<<1|1].tag4,p[u].tag4);
if(!p[u<<1].ok)
p[u<<1].tag2=max(p[u<<1].tag2,p[u<<1].tag1+p[u].tag2);
else
p[u<<1].tag4=max(p[u<<1].tag4,p[u<<1].tag3+p[u].tag2);
if(!p[u<<1|1].ok)
p[u<<1|1].tag2=max(p[u<<1|1].tag2,p[u<<1|1].tag1+p[u].tag2);
else
p[u<<1|1].tag4=max(p[u<<1|1].tag4,p[u<<1|1].tag3+p[u].tag2);
p[u<<1].tag3=p[u<<1|1].tag3=p[u].tag3;
p[u<<1].ok=p[u<<1|1].ok=1;
}
else{
p[u<<1].maxb=max(p[u<<1].maxb,p[u<<1].maxa+p[u].tag2);
p[u<<1|1].maxb=max(p[u<<1|1].maxb,p[u<<1|1].maxa+p[u].tag2);
p[u<<1].maxa+=p[u].tag1;
p[u<<1|1].maxa+=p[u].tag1;
if(p[u<<1].ok){
p[u<<1].tag4=max(p[u<<1].tag4,p[u<<1].tag3+p[u].tag2);
p[u<<1].tag3+=p[u].tag1;
}
else{
p[u<<1].tag2=max(p[u<<1].tag2,p[u<<1].tag1+p[u].tag2);
p[u<<1].tag1+=p[u].tag1;
}
if(p[u<<1|1].ok){
p[u<<1|1].tag4=max(p[u<<1|1].tag4,p[u<<1|1].tag3+p[u].tag2);
p[u<<1|1].tag3+=p[u].tag1;
}
else{
p[u<<1|1].tag2=max(p[u<<1|1].tag2,p[u<<1|1].tag1+p[u].tag2);
p[u<<1|1].tag1+=p[u].tag1;
}
}
p[u].ok=0;p[u].tag1=p[u].tag3=p[u].tag2=0;p[u].tag4=-1e18;
}