|
|
##[$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;
|
|
|
}
|
|
|
``` |
