【求助】关于FHQ-Treap的结点cnt(权值重复次数)附加域
  • 板块学术版
  • 楼主2020kanade
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/12/19 22:33
  • 上次更新2023/10/28 14:01:56
查看原帖
【求助】关于FHQ-Treap的结点cnt(权值重复次数)附加域
456724
2020kanade楼主2021/12/19 22:33

之前看到了这篇博客讲FHQ-Treap如何做到有交集情况下单log合并,然而里面的附加域cnt本人不知道怎么实现......然后就瞎搞了一个像甩棍一样的写法:需要按照排名分裂时如果子树大小分界点在某个结点上,就把结点裂成两个:新建一个子结点,权值和随机权值与原结点一致,挂在当前结点的左儿子上,当前结点的左子树挂到新结点的左儿子上,cnt按照分割界限分配,合并时直接用上面那篇博客中的方法

然而这种写法有个大缺点:在名次数getkth(查询排名为k的值)时,本人的写法需要按排名分裂,而此时的分裂会把不该切的点切开导致结果出错。现在有四种想法:

1.单独维护名次:显然太恶心了(可能只是本人懒+蒻);

2.getkth时避开分裂操作:本人也做不到,写了半下午次次RE(强迫症,拿指针写的......);

3.在getkth之前从树根进行一次dfs,把切开的在一条链上的连续区间的点合起来,getkth时按排名分裂不允许把点切开:也不行,dfs复杂度 O(n)O(n) ,并且不能保证能把所有点合起来;

4.3中的dfs改为把树重新合并一次(从根的左或右儿子处断开,方法同上面博客中的),其余相同:可行性本人无法证明,不过相比以上三种好像是最高的......

求各位神犇指点,多谢

2021/12/19 22:33
加载中...