P5494 题解 & 平衡树合并
DaydreamWarrior
·
·
题解
或许更好的阅读体验
这是一篇平衡树合并题解，平衡树合并的复杂度 并不是假的，本题复杂度 O(n \log n)，更通用的可以证明到 O(\log^2 n)，比如支持序列 全局加全局取膜。
平衡树比线段树适用性更广，常数也不大（未卡常无旋 treap 用时 615ms），注意下文 n,V 不分。
平衡树合并
先不考虑分裂，单说合并。
现在要合并 x,y 两棵树，选根节点堆值大的当根（假设是 x），把 y 的子树按照 x 的键值裂开（这里的裂开就是 treap 的 split），裂开的两瓣和 x 的左右儿子递归下去合并。
int Merge(int x,int y){
if(!x||!y)
return x|y;
if(tr[x].pri<tr[y].pri)
swap(x,y);
int l,r;
split(y,tr[x].v,l,r);
tr[x].l = Merge(tr[x].l,l);
tr[x].r = Merge(tr[x].r,r);
pushup(x);
return x;
}
明显是把小的树裂开更优，但是堆值大大概率就是树大的，下文也默认此情况（主要是带有随机的不会分析）。
其实这里存在一个合不合并相同结点的问题，其实是 要合并 的，因为 treap 的复杂度依赖于树和堆的唯一性，如果存在相同结点那么可能会失去性质（比如全部都一样，可以在不违反树和堆的情况下出来一条链），对于一般的 treap 不存在此问题，因为自带了一个插入时间的比较。注意这里代码没写。
现在分析平衡树合并的复杂度，设第一棵树大小为 a，第二棵为 b，不难发现单次合并的复杂度 上界 为 O(\min(a,b)\log(\frac{\max(a,b)}{\min(a,b)}))，大概是把小的树每个节点都拿去切割大的树，由于 finger search 所以切割复杂度为 \log(\frac{\max(a,b)}{\min(a,b)})。总复杂度为 O(n \log n)。
为什么说是上界，因为在两颗树值域重合少的时候复杂度和值域段数 k 有关，合并一次的复杂度为 O(k \log n)。
值域段数是指把所有值排序后相邻两个值属于不同树的个数。
本题的复杂度分析
可以直接用森林的值域段数作为势能，一次 split 会增加 1，一次 O(k\log n) 的合并会减少 k，所以时间复杂度为 O(n \log n)。
可以把合并的过程看作填空，split 过的地方就是空的分割线。
{[-----][\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ][\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ][\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ][-----]}
$$
{[-----][\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ][-----][\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ][-----]}
$$
那现在填上了，代价是 $O(2\log n)$，第二个 $][$ 的左边被用过了，第三个的右边被用过了。
一个 split 的左右会各被填一次，填一次的代价为 $O(\log n)$。
通过这个方法分析无 split 的 merge 也能得到 $O(n\log n)$ 的时间复杂度。
## 更通用的复杂度分析
定义势能为 $\varphi(T)=\sum\log(v_{i+1}-v_i)$，也就是 $T$ 相邻的两个值的差的 $\log$ 之和。
合并 $A$ 和 $B$，有 $k$ 段值域：
$$
\begin{aligned}
&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ _{<-d_1->}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ _{<--d_2-->}\ \ \ \ \ \ \ \ \ \ _{<--d_3-->}\ \ \ \ \ \ \ \ \ \ _{<---d_4--->}\\
&A = \{_{[--a_1--]}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ _{[-a_2-]}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ _{[--a_3--]}&\}\\
&B = \{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ _{[---b_1---]}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ _{[-b_2-]}&\}
\end{aligned}
$$
形如 $_{[-----]}$ 的是一段值域，形如 $_{<--d_i-->}$ 的是值域之间的距离且距离为 $d_i$。
合并后 $\Delta\varphi=\varphi(A)+\varphi(B)-\varphi(A\cup B)$，有
$$
\Delta\varphi=\log(d_1+b_1+d_2)+\log(d_2+a_2+d_3)+\dots+\log(d_{k-1}+a_{\frac{k}{2}}+d_k)-(\log d_1+\dots+\log d_k)
$$
前面的把 $\log(+a_i+)$ 的放在一起就是根据定义算的 $\varphi(A)$，后面的则是由于两段值域不交合并会产生新的势能，势能大小为 $\log$ 值域的距离也就是 $\log(d_i)$。
显然有
$$
\Delta\varphi\geq\log(d_1+d_2)+\log(d_2+d_3)+\dots+\log(d_{k-1}+d_k)-(\log d_1+\dots+\log d_k)
$$
因为 $\log$ 函数是上凸的，可得 $\log(\frac{a+b}{2})\geq \frac{\log a+\log b}{2}$，把 $\log$ 里的 $\frac{1}{2}$ 拿出来可得
$$
\log(a+b)\geq 1+\frac{\log a+\log b}{2}
$$
那么把 $\log(d_{i-1}+d_i)$ 全部拆开，可得
$$
\Delta\varphi\geq k-1-\frac{d_1+d_k}{2}
$$
忽略常数可得
$$
\Delta\varphi\geq k-O(\log V)
$$
也就是说最多做 $n \log V$ 次 split，总复杂度为 $O(n \log V \log n)$。
## 势能变化
一次分裂会减少 $\log V$ 的势能。
一次合并如果增加就至多增加 $\log V$ 的势能（原因可以看上面的式子）。
那么最多就只有 $n\log V$ 的势能，而 $\Delta \varphi$ 最大就是把这些势能都减少完，所以总复杂度为 $O(n \log n \log V)$。
## 代码
```cpp
const int N = 200005;
int n,m;
mt19937 myrand(713);
class fhqtreap{
private:
struct{int l,r,v,s,siz;unsigned pri;} tr[2*N];
int rt[N];
int idx;
int create(int v,int s){tr[++idx] = {0,0,v,s,s,myrand()};return idx;}
void pushup(int u){tr[u].siz = tr[tr[u].l].siz+tr[tr[u].r].siz+tr[u].s;}
public:
int& operator [] (const int &x){return rt[x];}
void split(int u,int c,int &x,int &y){
if(!u){
x = y = 0;
return;
}
if(tr[u].v<=c){
x = u;
split(tr[u].r,c,tr[x].r,y);
}
else{
y = u;
split(tr[u].l,c,x,tr[y].l);
}
pushup(u);
}
void split_rk(int u,int c,int &x,int &y){
if(!u){
x = y = 0;
return;
}
if(tr[tr[u].l].siz+tr[u].s<=c){
x = u;
split_rk(tr[u].r,c-tr[tr[u].l].siz-tr[u].s,tr[x].r,y);
}
else{
y = u;
split_rk(tr[u].l,c,x,tr[y].l);
}
pushup(u);
}
int merge(int x,int y){
if(!x||!y)
return x|y;
if(tr[x].pri>tr[y].pri){
tr[x].r = merge(tr[x].r,y);
pushup(x);
return x;
}
tr[y].l = merge(x,tr[y].l);
pushup(y);
return y;
}
int Merge(int x,int y){
if(!x||!y)
return x|y;
if(tr[x].pri<tr[y].pri)
swap(x,y);
int l,r;
split(y,tr[x].v,l,r);
tr[x].l = Merge(tr[x].l,l);
tr[x].r = Merge(tr[x].r,r);
pushup(x);
return x;
}
void insert(int &u,int c,int s){
int x,y;
split(u,c,x,y);
u = merge(merge(x,create(c,s)),y);
}
int kth(int &u,int K){
int x,y;
split_rk(u,K-1,x,y);
int p = y;
while(tr[p].l)
p = tr[p].l;
u = merge(x,y);
return p?tr[p].v:-1;
}
int count(int &u,int l,int r){
int x,y,z;
split(u,l-1,x,y);
split(y,r,y,z);
int ans = tr[y].siz;
u = merge(merge(x,y),z);
return ans;
}
void move(int &x,int &y,int l,int r){
int a,b,c;
split(x,l-1,a,b);
split(b,r,b,c);
y = b;
x = merge(a,c);
}
}tr;
signed main(){
n = in,m = in;
for(int k=1;k<=n;k++)
tr.insert(tr[1],k,in);
int idx = 1;
while(m--){
int op = in,p = in;
if(!op){
int x = in,y = in;
tr.move(tr[p],tr[++idx],x,y);
}
else if(op==1){
int t = in;
tr[p] = tr.Merge(tr[p],tr[t]);
}
else if(op==2){
int x = in,q = in;
tr.insert(tr[p],q,x);
}
else if(op==3){
int x = in,y = in;
out(tr.count(tr[p],x,y),'\n');
}
else
out(tr.kth(tr[p],in),'\n');
}
return 0;
}
```
### 全局加全局取膜
全局加不影响势能。
如果取模的过程中把树分成了 $k$ 段，合并后产生了至多 $(k-1) \log v$ 的势能，但是 $v$ 也会变成 $\dfrac{v}{k}$。把 $\log v$ 提到外面来，显然每轮最劣的 $k$ 都是一样的，因为这是一个递归的问题。原问题变成了 $k$ 使得 $k\log_k n$ 最大。解得最小值取 $e$，最大值为 $n$。所以增加的势能最大为 $n \log v$。
所以总复杂度为 $O(n \log n\log v)$。
### 通用性
确实这东西很能拓展，只要不咋影响势能都可以把合并当作基本操作，比如加、除、取膜、开根、翻转。
其实全局取膜作用与值域区间也是对的，值域区间完全可以把它当成两个独立的序列分别操作后再 merge 起来，分别操作也就是 $(n-m)\log v+m \log v= n\log v$，完全不影响。最后只是常数段的 merge 新增的 $\log v$ 的势能。所以只会增加总共 $n \log v$ 的势能，别的同理。
### 参考
[https://codeforces.com/blog/entry/108601](https://codeforces.com/blog/entry/108601)