发现惊天大秘密,用二分找前驱后继的话,如以下一组数据。
假设我们有这样两个区间 [1983,1993]和[1989,1996] ,并且这样是最后两个区间。然后我们在一开始加入了一个[0,2e9]的大区间,这样我们得出的[1983,1993]的后继就是[0,2e9]了,因为我们二分时是l<=r,那么最后一个[0,2e9] 会被判断一次,并且他的左端点恒小于上述区间,这样就错了!!!!!
P.S. 这是我把真正数据搞到后发现的,这样的写法导致最后他的答案少了1,但实质上答案数据确实是少了1的答案...这是因为有一个处理之后的区间是[993,1001],但是他的右端点已经大于1000(这组数据中的m)了,我们不会处理它,但是他是必须的,因为我们最后只能跑到[1983,1993],然后通过区间[1989,1997]跑是错误的,这样并不优,因为其实用[1993,2001]才对(就是上述的[993,1001]),因此本人认为只是把处理后右端点不超过m的区间加倍是错误的,就算右端点过了m也要加倍,这样才是对的。(如果有不对的地方还请大佬指出)
by NeosKnight @ 2018-07-25 21:00:33
如果有写BIT找前驱后继并且一直WA的要感谢我帮了你们啊....
by NeosKnight @ 2018-07-25 21:02:03
感谢
by 辰星凌 @ 2020-04-18 17:47:29
万分感谢!!!
by cqbzly @ 2020-08-27 22:27:13