线段树合并

简介

感觉跟 $dsu$ 挺像的一个东西人，如果一个东西要 $dsu$ 里面套线段树的话，完全可以直接用线段树合并

复杂度跟线段树总点数有关，因为合并每递归一次都会删一个节点

合并的代码大概是这样，可以打标记一类的

void merge(int &i, int j, int l, int r) {
    if (!i) return i = j, void();
    if (!j) return ;
    if (l == r) {
        T[i].s += T[j].s, T[i].v = l; 
        if (!T[i].s) T[i].v = 0; return ;
    } int m = l + r >> 1; pushdown(i, l, r);
    merge(lc, Lc, l, m); merge(rc, Rc, m + 1, r);
    maintain(i); 
}