##[$P5494$ 【模板】线段树分裂](https://www.luogu.com.cn/problem/P5494)

### 一、题目描述

给出一个可重集 $a$（编号为 $1$），它支持以下操作：

`0 p x y`：将可重集 $p$ 中大于等于 $x$ 且小于等于 $y$ 的值移动到一个新的可重集中（新可重集编号为从 $2$ 开始的正整数，是上一次产生的新可重集的编号$+1$）。

`1 p t`：将可重集 $t$ 中的数放入可重集 $p$，且清空可重集 $t$（数据保证在此后的操作中不会出现可重集 $t$）。

`2 p x q`：在 $p$ 这个可重集中加入 $x$ 个数字 $q$。

`3 p x y`：查询可重集 $p$ 中大于等于 $x$ 且小于等于 $y$ 的值的个数。

`4 p k`：查询在 $p$ 这个可重集中第 $k$ 小的数，不存在时输出 $-1$。

**输入格式**
第一行两个整数 $n,m$，表示可重集中的数在 $1\sim n$ 的范围内，有 $m$ 个操作。

接下来一行 $n$ 个整数，表示 $1 \sim n$ 这些数在 $a$ 中出现的次数 $(a_{i} \leq m)$。

接下来的 $m$ 行每行若干个整数，第一个数为操作的编号 $opt$（$0 \leq opt≤4$），以题目描述为准。

**输出格式**
依次输出每个查询操作的答案。

### 二、线段树的分裂 & 合并

网上找线段树合并/分裂的博客，讲得很清楚的也不多，某些部分只有自己 $yy$ 一下了。

**前置芝士**： **① 权值线段树**，**② 动态开点线段树**

在以下讨论中，我们设 **值域** 都为 $[1,n]$ 中的整数。

先定义代码中的一些东西：

$ch[i][0]$ 表示 $i$ 的左子结点，$ch[i][1]$ 表示 $i$ 的右子结点，$val[i]$ 表示 $i$ 点维护的值（出现了多少个该值域中的数）

#### 一、线段树合并
有时我们需要 **整合两棵权值线段树的信息** ，这个整合的过程称为 **线段树合并**。我们以最简单的合并为例：将两棵树相加。

两棵树如何相加呢？在权值线段树上，每个点维护了一个当前区间中数的个数，而数的个数是可以相加的，这个合并的过程可以理解为：**把两个可重集合并**，对应的权值线段树上发生的过程。而相加的原理很简单，两棵同构的线段树，只需要对应位置相加即可，如图：

<center><img src='https://cdn.luogu.com.cn/upload/image_hosting/lersbjt4.png'></center>

注意动态开点线段树上某些点是缺的，其值当然是 $0$。

如何合并两棵线段树呢？

暴力是很简单的，我们枚举 $1$ 到 $n$，将第二棵树中对应位置上的值在第一棵树上做单点修改即可。

这个方法可以用 **启发式合并** 进一步优化，但只能适用于一些特殊情况（比如说如果带了分裂或者一个值在多棵树上出现，启发式合并就歇菜了）。

而我们可以递归处理线段树合并，设我们现在要合并的是以 $x,y$ 为根的两棵子树，要确保它们在线段树上处于同一位置（即它们是两棵树上代表同一区间的点）。


如果 $x,y$ 其中一个为 $0$ （也就是某个权值线段树上没有这个位置的点），无需合并，返回另一个非 $0$ 的点即可。

否则，我们先合并 $x,y$ 的左右子结点，再根据两子结点的信息整合得到 $x,y$ 合并的结果。

线段树合并一般有两种写法：新建结点和不新建结点。但是两者原理是一样的。

**新建结点的写法**：

新建一个结点 $p$ 作为 $x,y$ 合并的结果。将 $ch[x][0]$ 和 $ch[y][0]$ 的合并结果记为 $sl$，$ch[x][1]$ 和 $ch[y][1]$ 的合并结果记为 $sr$，令 $sl,sr$ 分别为 $p$ 的两个子结点，对 $p$ 做一次 $pushup$​ 即可得到结果。此后 $x,y$ 就没有用的，可以回收（节省空间的方法）。但是有时 $x,y$ 的信息不能丢，这时就不能回收。

（这里原先的代码有点问题，先删了）

**不新建结点的写法：**
如果一个点合并完就可以扔掉，那还可以写得更加简便，直接将 $x$ 作为合并后的结果，将 $y$ 的值加到 $x$ 上即可（直接对应位置相加），甚至不需要 $pushup$，但是注意，如果 $x=0$，返回的是 $y$，所以比较保险的写法是 $x=merge(x,y)$。

事实上这里我们连当前区间的左右端点 $l,r$ 也可以去掉，因为到叶结点后 $ch[x][i]$ 自然是 $0$，自然会返回。

```cpp {.line-numbers}
int merge (int x,int y) {
    if (!x||!y) {return x+y;}     // 只有一边有点，不用合并
    val[x]+=val[y];               // 信息整合
    ch[x][0]=merge(ch[x][0],ch[y][0]);
    ch[x][1]=merge(ch[x][1],ch[y][1]);
    del(y);                       // 垃圾回收
    return x;
}
```
这东西看着很一般，复杂度怎么样呢？

单独讨论一次合并的复杂度没有什么意义，如果两棵树都是满的，复杂度就到 $O(n)$ 了，所以一般从均摊角度来讨论。


如果现在有 $m$ 棵线段树（每棵树初始只有一个位置有权值），经过若干次合并最后变成 $1$ 棵，此过程的复杂度是多少呢？

**例题**：
[$P4556$ [$Vani$有约会]雨天的尾巴 /【模板】线段树合并](https://www.luogu.com.cn/problem/P4556)

[$P5298$ [$PKUWC2018$]$Minimax$](https://www.luogu.com.cn/problem/P5298)

不说具体怎么做了，这些题都有很完整的题解，我就分析一下复杂度（这些题都符合上面提到的模型）。

一开始有 $m$ 棵树，只有一个位置有权值，所以一棵树上结点数量为 $O(logn)$，$m$ 棵树的结点总数也就是 $O(mlogn)$。

分析上面的代码，发现每一次进入 $merge$ 函数，要么停止递归，要么继续递归并有一个点被垃圾回收。显然停止递归的 $merge$ 次数与继续递归的 $merge$ 次数同阶（不继续递归的情况是从递归的情况出来的，不会超过其两倍的数量）。

因此整个过程的复杂度就等于继续递归的 $merge$ 函数进入次数的复杂度（每一次执行 $merge$ 在不考虑递归时复杂度 $O(1)$），也就等同于被删除的结点个数，是不超过 $O(mlogn)$ 的（有点像势能分析？）。

注意复杂度本身和是否回收结点没有关系，只是借以分析而已。

所以整个过程的复杂度也就是 $O(mlogn)$。

但是线段树合并的复杂度不总是对的，不过本题中 $1$ 操作的复杂度我不知道是否是均摊 $logn$ 的，希望有人能证明/证伪一下。

#### 二、线段树分裂
将一个可重集前 $k$ 小的数与之后的数分成两个集合，那么对应的权值线段树就要裂成两棵权值线段树。

举个栗子：将 $[1,3]$ 和 $[4,4]$ 分开（这里为了方便直接用权值描述了，一般是按照第 $k$ 小的位置来的）：

<center><img src='https://cdn.luogu.com.cn/upload/image_hosting/g0vypgpq.png'></center>

暴力当然也很简单，找到第 $k$，后面的值新建一棵树，在原树上减掉即可。

然而我们可以仿照 $FHQ$ $Treap$ 的套路，实现 $O(logn)$ 的分裂。


设我们现在要将以 $x$ 为根的树分裂成 $x,y$ 为根的这两棵树（$y$ 本来是不存在的，传引用），以第 $k$ 小为界，前 $k$ 小在 $x$，之后的在 $y$。

首先看 $x$ 的左子树的值 $v$，如果 $v<k$，那么左侧依然归 $x$（不需要处理），递归右侧即可，注意 $k$ 变成了 $k-v$。

如果 $v=k$，那么左边归 $x$，右边归 $y$ 即可。

如果 $v>k$，那么右边归 $y$，递归左侧即可。

看完结构后看权值，$x$ 的新权值当然是 $k$，那么 $y$ 的权值也就是 $x$ 原先的权值减去 $k$ 了。

可以发现，如果 $v\ge k$，那么 $y$ 的右子结点都是需要赋值的，下面的代码直接归到了同一句里（`else` 所在的那一句）：

```cpp {.line-numbers}
void split (int x,int &y,ll k) {
    y=newnod();
    ll v=val[ch[x][0]];
    if (k>v) {split(ch[x][1],ch[y][1],k-v);}
    else {swap(ch[x][1],ch[y][1]);}         // 右子树归 y，x 的右子树变成 0
    if (k<v) {split(ch[x][0],ch[y][0],k);}
    val[y]=val[x]-k;
    val[x]=k;
    return;
}
```
这个每次只递归一边，复杂度是 $O(\log n)$ 没啥问题。

#### 三、这道题

每个操作分别来看。

将 $[x,y]$ 分裂出来：先分出 $[1,x-1]$，再从 $[x,n]$ 中分出 $[x,y]$ 和 $[y+1,n]$，最后把 $[1,x-1]$ 和 $[y+1,n]$ 合并。我注意到 $std$ 不是这样的，$std$ 的分裂写的就是分裂出一个区间，我在这里用了一次合并，但是复杂度是对的，稍后会证明复杂度为 $O(\log n)$；

将 $t$ 树合并入 $p$ 树：单次合并即可，不确定复杂度，但是不超过 $2\times 10^3$次总没问题的；

$p$ 树中插入 $a$ 个 $q$：单点修改，复杂度 $O(\log n)$；

查询 $[x,y]$ 中数的个数：区间求和，复杂度 $O(\log n)$；

查询第 $k$ 小：经典操作，复杂度 $O(\log n)$。

最后说一下 $0$ 操作的复杂度：

两次分裂是 $O(\log n)$ 没问题，主要看合并。注意合并的两个区间没有交集，我们就看一看每一层会涉及几个点。

对于第 $1$ 层：总共就 $1$ 个点...

对于第 $i$ 层：如果第 $i-1$ 层只递归下来 $1$ 个点（设为 $u$），再设 $x$ 和 $y$ 为 $u$ 的左右子结点。如果前一棵树占了 $x,y$ 两个点，那么因为后一棵树占的区间严格在前一棵树之后，所以只会占 $y$，那么需要递归的只有 $y$，反过来的话同理需要递归的只有 $x$，所以第 $i$ 层也只需要递归 $1$ 个点。

每一层只往下递归一个点，复杂度就是 $O(\log n)$ 了。

### 三、实现代码
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
//重定向输入输出
#define FILE_OUT freopen("P5494.out", "w", stdout);
#define FILE_IN freopen("P5494.in", "r", stdin);

//重定义 tr[u].l 和 tr[u].r 快速录入用
#define ls tr[u].lson
#define rs tr[u].rson

const int N = 200010;
int n, m;
int a[N]; //记录原始数组，其实也可以不用保存，直接在build时录入到叶子也可以

int root[N], idx; //分裂出的第几个线段树,idx是序号维护器

struct Node {
    int lson, rson; //动态开点,记录左右儿子的节点编号
                    //注意：这里与普通线段树不同，没有记录当前节点的管辖范围！！！！！
                    //黄海尝试了记录[l,r]的方法，结果因为结构体内增加了两个属性，同时数组的上限非常大，直接MLE了好多测试点。
    LL val;         //每一个节点保存的值大小是管辖区间中的个数
} tr[N << 6];
int cnt; //记录tr数组中的可以放入节点的位置

//权值线段树合并,维护区间元素个数
void pushup(int u) {
    tr[u].val = tr[ls].val + tr[rs].val;
}

/**
 * @brief 构建线段树
 *
 * @param l 想要创建的节点，是管理哪个范围的，这与普通线段树相似，只不过普通线段树可以事先准备好节点号，这个需要现用现创建，
 * 并且需要返回节点号，让父节点记录和父节点的关联关系。
 * @param r
 * @return int
 */
int build(int l, int r) {
    //由于构建之前，空间是未分配状态，需要为新构建的节点分配节点号，节点号就是cnt
    int u = ++cnt;
    //现在有了可用的节点号了
    if (l == r) { //如果是叶子节点
        //接下来一行n个整数，表示 1∼n 这些数在a[N]中出现的 **次数**
        //其实7就放在[7,7]的位置上，val就记录7这个数字出现的次数
        tr[u].val = a[l]; //个数！！！
        return u;
    }
    int mid = (l + r) >> 1;

    //由于是动态开点，无法像普通线段树一样，采用预先创建的办法，普通办法只要知道父节点，u<<1 和 u<<1|1就是左右儿子节点号
    //而在动态开点的模板中，需要递归创建并返回新建节点编号，由并记录到tr[u].l和tr[u].r上，以实现父子节点的关联对应
    ls = build(l, mid), rs = build(mid + 1, r);
    //更新父节点统计信息
    pushup(u);
    return u;
}
/**
 * @brief 线段树分裂
 *
 * @param k 以k为根的线段树
 * @param l 左边界
 * @param r 右边界
 * @param ql 要分裂出的左边界
 * @param qr 要分裂出的右边界
 * @return int
 */
int spilt(int k, int l, int r, int ql, int qr) {
    int u = ++cnt;                         //分裂后的根节点编号u
    if (l == ql && r == qr) {              //完全命中区间
        tr[u] = tr[k];                     //将tr[k]抄到tr[u]
        tr[k].val = tr[k].lson = tr[k].rson = 0; //销毁tr[k]
        return u;                                //返回新分裂后的节点编号u
    }
    int mid = (l + r) >> 1;
    if (qr <= mid) //分裂左儿子
        ls = spilt(tr[k].lson, l, mid, ql, qr);
    else if (ql > mid) //分裂右儿子
        rs = spilt(tr[k].rson, mid + 1, r, ql, qr);
    else {
        ls = spilt(tr[k].lson, l, mid, ql, mid);
        rs = spilt(tr[k].rson, mid + 1, r, mid + 1, qr);
    }
    //递归更新分裂后u和k的父节点信息
    pushup(u), pushup(k);
    return u;
}

//合并线段树
void merge(int &x, int y) {
    if (!(x && y))
        x |= y;
    else {
        tr[x].val += tr[y].val;
        merge(tr[x].lson, tr[y].lson);
        merge(tr[x].rson, tr[y].rson);
    }
}

/**
 * @brief 在 u 这个可重集中加入 x 个数字 q
 *
 * @param u 以u为根
 * @param l 左边界
 * @param r 右边界
 * @param q 数字p
 * @param x 增加x个
 */
void insert(int u, int l, int r, int q, int x) {
    if (l == r) {
        tr[u].val += x; //权值线段树个数增加x个
        return;
    }
    int mid = (l + r) >> 1;
    if (q <= mid) {
        if (ls == 0) ls = ++cnt;  //左儿子不存在，则创建之
        insert(ls, l, mid, q, x); //向左儿子递归插入
    } else {
        if (rs == 0) rs = ++cnt;      //右儿子不存在，则创建之
        insert(rs, mid + 1, r, q, x); //向右儿子递归插入
    }
    //向父节点更新统计信息
    pushup(u);
}
/**
 * @brief 在以u节点为根的线段树中，管辖范围是[l,r],查询区间[ql,qr]内数字的总个数
 *        查询可重集 p中大于等于 x 且小于等于 y 的值的个数。
 * @param u 根节点
 * @param l 左边界
 * @param r 右边界
 * @param ql 查询左边界
 * @param qr 查询右边界
 * @return LL 有多少个
 */
LL query(int u, int l, int r, int ql, int qr) {
    if (l == ql && r == qr) return tr[u].val;
    int mid = (l + r) >> 1;
    if (qr <= mid)
        return query(ls, l, mid, ql, qr);
    else if (ql > mid)
        return query(rs, mid + 1, r, ql, qr);
    else
        return query(ls, l, mid, ql, mid) + query(rs, mid + 1, r, mid + 1, qr);
}

//查询第k小的数
int kth(int u, int l, int r, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (tr[ls].val >= k)
        return kth(ls, l, mid, k);
    return kth(rs, mid + 1, r, k - tr[ls].val);
}

int main() {
// OJ的环境不使用文件输入输出
#ifndef ONLINE_JUDGE
    FILE_IN
    FILE_OUT
#endif
    //优化读入
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    //范围[1~n],创建第一个线段树，返回值是根节点号，记录到root[1]中
    for (int i = 1; i <= n; i++) cin >> a[i];
    root[++idx] = build(1, n);

    int op, p, x, y;
    for (int i = 1; i <= m; i++) {
        cin >> op >> p;
        if (op == 0) { //将可重集p中大于等于x且小于等于y的值放入一个新的可重集中
            //新可重集编号为从2开始的正整数，是上一次产生的新可重集的编号+1。
            cin >> x >> y;
            root[++idx] = spilt(root[p], 1, n, x, y);
        } else if (op == 1) { //合并线段树
            cin >> x;
            merge(root[p], root[x]); //将根为x的线段树合并到根为p的线段树中去,x线段树以后就不用了
        } else if (op == 2) {        //在p这个可重集中加入x个数字q
            cin >> x >> y;
            insert(root[p], 1, n, y, x);
        } else if (op == 3) { //区间查询
            cin >> x >> y;
            printf("%lld\n", query(root[p], 1, n, x, y));
        } else {
            int k;
            cin >> k; //在线段树上二分，如果左孩子的元素个数大于等于k，说明第k小在左子树内；
            //否则，在右子树内。
            if (query(root[p], 1, n, 1, n) < k)
                printf("-1\n");
            else
                printf("%d\n", kth(root[p], 1, n, k));
        }
    }
    return 0;
}
```