洛谷2471


题意:给定一些(n个)按升序排好的年份和对应的降雨量,年份不会重复,但是有可能会遗漏。又有q个描述(x,y),描述的是“y年的降雨量是继x年以来最高的”,如果 降雨量x>=降雨量y 且对于任意的x<z<y,都有 降雨量z<降雨量y ,那么我们说这句话是“对的”。如果找的到x,y,z不满足上述关系,那么这句话是“错的”,否则这句话是“可能对”的(因为遗漏年份的降水量无法确定)。$(n,k<=5*10^4)$

对于所有对的的描述,输出"true",错的输出"false",可能对的输出"maybe"。

思路,我们可以通过判断以下几个量来获得这句话的真伪

x,y是否已知

x.val,y.val(即x,y年的降水量)

(x,y)区间内是否有未知量

(x,y)区间内的最大值mx

true.这句话是真的当且仅当:

lr已知,l.val>=r.val,mx<r.val,(x,y)内无未知量

maybe.这句话可能为真当且仅当下面一项成立:

lr未知

l知r未知,r.val>mx

l未知r知,mx<r.val

lr已知,mx<r.val,l>=r.val

false.余下的情况这句话不成立

因此,这道题只需要建立线段树保存区间最大值,区间是否有未知年份,区间的左右端是否有未知年份即可,只是讨论比较复杂.