如果你WA#9
查看原帖
如果你WA#9
240724
FFFFFAN楼主2023/8/7 17:56

我的错法:开始时先把宽高都减一,然后去跑正常的先加后删的离散扫描线。

正确做法:宽高不用减一,并且改成先删后加

推测原因:离散线段树虽然端点在存储上是重合的,但是我们处理时还是当做左闭右开来处理,因此更新ans那一块就会有右端点mx不会被统计到的问题,在本题第9个点中刚好存在这种情况。因此如果按x排序,则高不该减一,只需要宽减一即可(已测试,确实可以AC)。另外一种不用考虑这个问题的做法就是改成都不减一,并且排序时先删后加,因为此时该删的星星已经被框挡住了,与减一的做法其实考虑的是一样的,这样也是正确的。

2023/8/7 17:56
加载中...