警示后人(用离散化+暴力的)

P3740 [HAOI2014] 贴海报

肖翔 @ 2023-10-03 07:59:36

https://www.luogu.com.cn/discuss/577634

这个讨论里的反例是有效的。

6 3
1 5
1 2
4 6

如果离散化了,

1->1

2->3

4->4

5->5

6->6

修改时1~2配上4~6,本来不会把3覆盖的,但离散化后会导致变成1~3和4~6,把3覆盖了,于是第二张海报被错误地覆盖了。

原因大概是离散化把不同端点之间的距离删了,每个都紧邻,当出现端点紧贴着的时候会因为忽略了中间距离导致答案变少。

而且出现这样的情况这样非常难处理,因为暴力+1或乘上某常数又会导致原本相邻的扩大,不再相邻,了导致答案变多。

所以还是写线段树吧。


by Hanx16Kira @ 2023-10-03 08:17:32

离散化是可行的,首先你举的例子当中离散化没有进行去重。

然后对于本来有间隔的变成了紧挨着的情况,考虑将每一个端点 x 的相邻点 x+1 也加入离散化数组。


|