我猛锌不理解

P2839 [国家集训队] middle

weijia33 @ 2023-07-07 19:09:44

AC 了,但不理解:

build(root[1] , 1 , n);
for (int i = 2 ; i <= n ; i++)
    upd(root[i] , 1 , n , root[i-1] , a[i - 1].ip);

当主席树建树时有 a[i].v == a[i - 1].v 的情况时,我们仍然在 i - 1 的版本上把1修改为 -1,而我们是将>=的改为-1,并且重合时所有重合的节点的版本不一样 这么建不会出锅吗


by Full_Speed @ 2023-07-07 19:28:11

具体的,我们的版本mid维护的是当当前值为mid-11的序列,但是当出现相等的情况时,那些不合法的版本是比合法的要小,我们希望前缀,后缀,子段和尽可能大,所以二分时会忽略这些不合定义的版本


by weijia33 @ 2023-07-07 19:30:48

懂了,谢谢大佬


|