如果你也像我这么写,并且除#25外全WA,可以看看这两点有没有做:
第一,同一水平线上的点若是最低点不能加入,但若是最高点则需要删除,可以考虑下面这样做。复杂度有保证吗?这个 for 每次只执行当前水平线上的点,所以一共最多执行 O(N) 遍。
for (int j = now; j <= N && pt[j].y == i; ++j) {
if (pt[j].y == top[pt[j].x] && bit.query(pt[j].x) - bit.query(pt[j].x - 1) == 1)
bit.modify(pt[j].x, -1);
}
第二,在最后记得特判一开始就有的黑点,比如这个 hack:
5
0 2
2 0
-2 0
0 -2
0 0