【USACO2008feb】【Luogu P2894】Hotel

线段树区间合并。可以先做CH4301

附加信息:区间长度len(方便),lazy tag(记录开房、退房)。

需要维护的信息:从左边开始的最长连续空房间lsum,从右边开始的最长连续空房间rsum,区间最长连续空房间dat。

不要按题中的1、2操作写两个主要函数,1操作写一个查询,1、2操作一起改变房间状态。

查询:两区间中间满足:返回;左边满足递归左子树,右边满足递归右边。时刻下传lazy tag。

修改:(核心,难点)

类似模板的区间操作,若当前区间被完整区间覆盖,则lsum,rsum,dat赋为0或区间长。

关键在上传。dat很简单,max(中间和,左dat,右dat)。

lsum,rsum要判断是否占满左/右区间,如果占满,则加上另一个区间的lsum/rsum。

另外,编译器用debug并打开-Wall可以避免低级错误。

原文地址:https://www.cnblogs.com/xzs123456/p/10449885.html