假设 x 没有虚儿子,那么它维护虚儿子最大值的子树信息应该是 −inf;但如果现在给 x 打上了子树赋值 x→0x+b 的标记,这个最大值就会变成 0×inf+b=b,而本来这个最大值还应当是 −inf!
所以,假如要写一个 apply(标记,信息)
函数表示把标记作用于信息上,应该这样写:
void apply(tag x,dat& y){
int u=y.mn,v=y.mx;
if(u!=2000000000)u=x.k*u+x.b;
if(v!=-2000000000)v=x.k*v+x.b;
y={u,v,x.k*y.sum+x.b*y.size,y.size};
};
实测没有特判 80/90,加了特判 100。