80/90 分的原因找到了!!
  • 板块P5649 Sone1
  • 楼主feecle6418机器人
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/8/27 19:38
  • 上次更新2023/11/4 08:47:26
查看原帖
80/90 分的原因找到了!!
42156
feecle6418机器人楼主2021/8/27 19:38

假设 xx 没有虚儿子,那么它维护虚儿子最大值的子树信息应该是 inf-inf;但如果现在给 xx 打上了子树赋值 x0x+bx\to 0x+b 的标记,这个最大值就会变成 0×inf+b=b0\times inf+b=b,而本来这个最大值还应当是 inf-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。

2021/8/27 19:38
加载中...