之前看到了这篇博客讲FHQ-Treap如何做到有交集情况下单log合并,然而里面的附加域cnt本人不知道怎么实现......然后就瞎搞了一个像甩棍一样的写法:需要按照排名分裂时如果子树大小分界点在某个结点上,就把结点裂成两个:新建一个子结点,权值和随机权值与原结点一致,挂在当前结点的左儿子上,当前结点的左子树挂到新结点的左儿子上,cnt按照分割界限分配,合并时直接用上面那篇博客中的方法
然而这种写法有个大缺点:在名次数getkth(查询排名为k的值)时,本人的写法需要按排名分裂,而此时的分裂会把不该切的点切开导致结果出错。现在有四种想法:
1.单独维护名次:显然太恶心了(可能只是本人懒+蒻);
2.getkth时避开分裂操作:本人也做不到,写了半下午次次RE(强迫症,拿指针写的......);
3.在getkth之前从树根进行一次dfs,把切开的在一条链上的连续区间的点合起来,getkth时按排名分裂不允许把点切开:也不行,dfs复杂度 O(n) ,并且不能保证能把所有点合起来;
4.3中的dfs改为把树重新合并一次(从根的左或右儿子处断开,方法同上面博客中的),其余相同:可行性本人无法证明,不过相比以上三种好像是最高的......
求各位神犇指点,多谢