肖翔 @ 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
离散化是可行的,首先你举的例子当中离散化没有进行去重。
然后对于本来有间隔的变成了紧挨着的情况,考虑将每一个端点