无值域不交要求的可并FHQ

前言

这个 trick 的来源是一篇 CF 上的博客，本文进行了部分翻译与一定的拓展。

FHQ 的合并有一个痛点：必须保证值域不交。但是本文给出了一种均摊分析方式，使得可以维护随意合并，分裂的 FHQ。

UPD 2024/11/15:文末资料处有一篇别人写的很详细的同样内容，一起食用效果更佳。

介绍

初始有若干棵 FHQ treap ，合并时将两个 FHQ 拆成若干值域不交的段，然后合并。写成代码是这样的。

int tr_merge(int x,int y){
  int z=0;
  while(x&&y){
    long long vx=get_min(x),vy=get_min(y);
    if(vx>vy) swap(vx,vy),swap(x,y);
    int w;split_by_val(x,vy,w,x);
    z=merge(z,w);
  }
  z=merge(z,x);z=merge(z,y);
  return z;
}

UPD 2024/11/15:这里应当要合并完全相同的节点，但是由于一般情况下每个点的key值都不同，所以也仍然正确，可以不用特别处理。

分裂的代码则不变，与正常的 FHQ 没有不同。

复杂度分析

对于一个有序序列 A=[x_1,x_2,\dots,x_n] 我们定义其势能函数如下。

\pi(A)=\sum_{i=1}^{n-1} \log(x_{i+1}-x_i)

借用一下 CF 老哥的图，接下来展开对各操作的分析。

假设此时要合并 A 序列和 B 序列，并且 A 与 B 中的值形成了 k 个连续段 a_1,a_2,\dots,a_{k/2},b1,b2,\dots,b_{k/2}，且值域相邻的连续段之间有距离 d_1,d_2,\dots,d_k。

\Delta\pi=\pi(A)+\pi(B)-\pi(A\cup B)

注意到同一值域段内由于间距为 1 所以 \log 为0。

-(\log(d_1)+\log(d_2)+\dots+\log(d_k))

进行放缩：

-(\log(d_1)+\log(d_2)+\dots+\log(d_k))

由 \log 函数是凹函数的经典性质，我们有：

\log(\frac{a+b}{2}) \ge \frac{\log(a)+\log(b)}{2}

推一下：\log(a+b)-\log(2) \ge \frac{\log(a)+\log(b)}{2}。
即 \log(a+b)-\frac{\log(a)+\log(b)}{2} \ge 1。
将其应用回式子进行一加一减：

-(\log(d_1)+\log(d_2)+\dots+\log(d_k))\textcolor{red}{-\log(d_k+d_1)} \Delta\pi \ge k-\log(d_k+d_1)

也就是说，每次合并两个颜色段为 k 的序列时，总势能至少减少 k-\log V，可以看做减少 k 又增加 \log V。同时容易发现序列合并后再拆开只会减小势能。初始时势能至多为 O(n\log V)，故总势能至多为 O((n+q)\log V)，加上 FHQ 的复杂度我们得到了 O((n+q)\log V\log n)。

以下给出一些例题，但是都不是正解，所以仅供参考。

P11244 吻秋

容易发现做的操作一模一样，直接维护即可，但是由于询问过多，无法通过本题。但是复杂度中没有 m 的存在，也不失为另一种加强。

代码

AT_joisc2015_m 防壁

考虑将一些左/右端点相同的线段看做一组，每一组用一棵 FHQ 维护该组的长度集合，容易发现一次激光会将左右两边的组进行合并 (1)，以及将其穿过的组进行分割 (2)。图示如下。

红色要并到线上；紫色也要并到线上；绿色要分成一组不动，一组并线；蓝色不变。

求解答案只需要在移动的过程中给整棵树打加法 tag 即可。

现在来分析一下时间复杂度。

先分析分裂操作，初始有 n 组，我们发现在任意时刻，如果暂时去掉那些从最开始就没被做过任何操作的线段，你没有办法构造出两个梯形的斜边所在区间相交。如图所示，你没法去掉没动过的线段后还保留以下任意两个相交的梯形。这个可以由详尽分讨证明，在此不再赘述。

于是分裂操作顶多 O(n+q) 次，左边是初始的线段个数，右边是每次激光新产生的次数之和。

现在考虑合并，发现由于分裂操作有保证，每次合并段数减少，分裂段数增加，于是容易分析出合并次数也是 O(n+q) 的。

于是我们得到了总复杂度为 O((n+q)\log V\log n) 的做法，虽然比正解慢10倍，但是在极其宽松的时限下依旧可以通过。

代码

资料链接

CF原博客链接："Merging treaps" -- or how to merge sorted sets in good complexity...

一篇别人写的更加详细且有例题的文章：P5494 题解 & 平衡树合并