复杂数据结构

P1 左偏树

定义：左偏树是一种带权树，权满足堆性质，且树的形态满足左偏性质。

左偏性质：左儿子到最近叶子节点的距离大于等于右儿子到叶子节点最近距离。

代码实现：

xxxxxxxxxx
17
1
merge(a,b){
2
    if(a==null)return b;
3
    if(b==null)return a;
4
    if(a->key>b->key)swap(a,b);
5
    a->rs=merge(a->rs,b);
6
    swap(a->rs,a->ls);
7
    return a;
8
}
9
merge(a,b){
10
    if(a==null)return b;
11
    if(b==null)return a;
12
    if(a->key>b->key)swap(a,b);
13
    a->rs=merge(a->rs,b);
14
    if(a->ls->npl<a->rs->npl)swap(a->rs,a->ls);
15
    a->npl=a->rs->npl+1;
16
    return a;
17
}

可以可持久化。

E1 BalticOI 2004 Sequence 数字序列

给一个长度为 $∑n$ 的序列 $a$，请求出一个单调递增序列 $b$，最小化 $\sum|a_i − b_i|$。$n \le 10^6$。

这是一个保序回归问题，用单调栈解决；但作为一次情况，它需要取所有量的中位数，并不能像二次情况那样快速地合并。所以我们用对顶的左偏树来解决合并两块的问题。

E2 Codeforces 414E

现给定 $m$ 次操作，每次操作是下列三种中的一种：

1. 给定 $u, v$，询问 $u, v$ 之间的距离。
2. 给定 $v, h$，断开 $v$ 到父亲的边，将 $v$ 这棵子树加入到它的第 $h$ 个祖先的最后一个儿子。
3. 给定 $k$，询问在当前这棵树上 dfs 后得到 dfs 序中，最后一个深度为 k 的点的编号。$n, m \le 10^5$。

经典套路，我们用 splay 维护这棵树的欧拉序，在进入一个点时加一，在退出一个点时减一。

首要的问题是，如何找到一个点的子树对应的区间？显然我们可以使这个区间的左端点就等于这个点的编号，问题是如何找到右端点。直接找到下一个前缀和等于左端点的前缀和减一的位置即可找到右端点。第二种操作也就解决了。

第二种操作是自然解决的；而第一种操作需要的是查找 lca，查询区间前缀和的最小值及其位置就行。

E3 Codeforces 806D

给定 $n$ 个区间，构造一个序列，每个数可以在区间里选 要求尽可能大的（严格上升）LIS，输出这个值 $m \le 10^5$。

按照传统 LIS 的求法，求出长度为 $i$ 的序列的最小的结尾，记为 $dp_j$。显然这个 $dp_j$ 是单调递增的，因为如果不递增我们大可以直接把长的那个缩短一些变成短的。

转移有三种：

我们找到最小的小于 $l$ 的 $j$ 转移到 $j+1$ 就可以实现转移一；由于递增的性质，直接右移一位就能实现转移二；转移三就是不修改。$O(n\log{n})$。

P2 SGT

令 $h$ 为树的深度，$n$ 为树的节点个数。

若 $h \le \log_{\frac 1{\alpha}} n$，则称这棵树为 $α$ 高度平衡；若 $h \le \log_{\frac 1{\alpha}} n + 1$，则称这棵树为宽松 $α$ 高度平衡

当 $n$ 一定时: $α$ 值越小，二叉搜索树越稠密，插入效率越低，查询效率越高；$α$ 值越大，二叉搜索树越稀疏，插入效率越高，查询效率越低。

若二叉搜索树的每个结点都满足以左右儿子为根的子树的大小分别小于等于以它为根的子树大小乘 $α$，则称它为 $α$ 权重平衡。如果一棵二叉搜索树 $α$ 权重平衡，那它一定 $α$ 高度平衡，反之不一定成立。为了保证复杂度，替罪羊树应当始终是宽松 $α$ 高度平衡的，但不一定需要是 $α$ 权重平衡的。

众所周知替罪羊树的“暴力”是 $O(n\log{n})$ 的。

后缀平衡树：给每个点赋一个实数权值区间，把左区间给左儿子，右区间给右儿子；直接比较权值的大小就能 $O(1)$ 比较两个点在先序遍历中的顺序；遇到不平衡的情况暴力重构。

E4 [SC2014] 方伯伯的玉米地

方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。这排玉米一共有 $N$ 株，它们的高度参差不齐。方伯伯认为单调不下降序列很美，所以他决定先把一些玉米拔高，再把破坏美感的玉米拔除掉，使得剩下的玉米的高度构成一个单调不下降序列。方伯伯可以选择一个区间，把这个区间的玉米全部拔高 $1$ 单位高度，他 可以进行最多 $K$ 次这样的操作。拔玉米则可以随意选择一个集合的玉米拔掉。问能最多剩多少株玉米，来构成一排美丽的玉米。$n \le 10000, k \le 500,a_i \le 5000$。

我们不妨先拔高，最后再来拔除；也就是说，拔高后求一个 LIS。又注意到，拔高一定是拔高一个后缀最优秀。

设 $f_{i,j}$ 表示前 $i$ 个点、以第 $i$ 个点结尾的、经过 $j$ 次拔高的 LIS。那么可以得到：

三维偏序优化 dp 即可（本题中直接用二维树状数组的实现是最理想的）。

E5 Codeforces 983D

给定 $n$ 个矩形，一个一个覆盖，问最后能看到几个矩形。$n \le 10^5$。

一般人的思路是把问题倒过来做，变成一个矩形 + 矩形求 min 的问题，但是我们发现这并不可做。

我们直接扫描线。定义每个矩形的权值为它加入的时间。建立一个线段树，线段树的每一个节点都维护一个 set1，存下所有包含这个区间的矩形权值。

一个重要的引理是，覆盖一个区间 $[l,r]$ 的颜色 $c$ 在这列中存在一个位置可以被看到，当且仅当区间 $[l,r]$ 到 $[1,n]$ 的整条路径的 set1 里，都不存在大于等于 $c$ 的颜色。因为对于其子树中的颜色，它可能

E6 Codeforces 1109F

给一个 $n\times m$ 的矩阵，矩阵元素是一个 $n\times m$ 元素的排列 问有多少区间 $[l, r]$ 满足将这个区间值提出来在四联通意义下是一棵树。$n\times m \le 2 × 10^5$。

树等价于没有环且点数等于边数加一。

对于没有环的条件，设 $fl_r$ 表示右边界为 $r$ 时最小的左边界 $l$ 使得 $[l,r]$ 无环，显然 $fl$ 是递增的。依靠 LCT 维护一个双指针即可。

对于点数等于边数加一的条件，依然是维护每个 $l$ 对应的 $[l,r]$ 的点数减边数，右边新加一个点相当于全部点的点数加一，至多四个后缀的边数加一。存下区间最小值和最小值个数即可。$O(n\log{n})$。

E7 Codeforces 603E

给出 $n$ 个点，$m$ 个操作，每个操作加入一条 $(u, v)$ 长度为 $l$ 的边。对于每次操作后，求出一个边集，使得每个点度数均为奇数，且边集的最大边最小。$n, m \le 10^5$。

一个边集存在一个子集使得点的度数，当且仅当所有连通块的大小都是偶数。因为如果连通块大小是奇数，那么度数不可能都是奇数，否则度数的总和就是奇数了；如果连通块大小是偶数，那么取出它的一棵生成树，即可自下而上构造出解。

添加一条边，其唯独的作用便是消去奇数连通块。连接两个偶数连通块或者一奇一偶的边只不过当前没有用而已；而同一个连通块，我们需要保留的紧紧是其 MST。

用 LCT 维护 MST 森林。依次加边，如果新加的边不能消去奇数连通块或者影响当前块 MST 的大小，也不能不加（因为在删边之后也许会派上用场）。我们 link 这条边，并断去它所在环上的最大边。每次修改结束后，我们不停判断当前最大的边连接的两棵子树是不是都是偶数，直接断去。

E8 Codeforces 1039E

给一个数列，每次询问一个 $x$，问序列分成最少几段满足每段极差不超过 $x$。$n, q \le 10^5$。

将 $x$ 离线排序，从小到大处理。根据贪心的性质，每个 $i$ 点都可以连一条边向确定的 $t_i$，每次查询相当于查询一个点的深度。随着 $x$ 的增大，$t_i$ 逐渐增大。尽管这个问题可以用 LCT 很快地维护，但无奈修改的次数高达 $O(n^2)$。

于是我们根号分治一下，对于每个 $i$，预处理出 $t_i$ 的前 $S+1$ 个增长点。随着 $x$ 的增加，我们会去更新每个点的前 $S$ 次增长；但当一个点的 $t$ 第 $S+1$ 次增长后，我们不再在 LCT 中连出这条边，而是再也修改它，留到询问时倍增处理。

对于每次询问，如果它处在一个未经过 $S$ 次增长的点上，则直接跳到它所在 LCT 的根上；否则使用倍增暴力找到它的 $t_i$ 并跳过去。由于上述两种必然是交错进行，而第二种操作必然会使当前点右移至少 $S$ 步，所以复杂度得到保证。$O(n^{1.5}\cdot\log{n})$。

事实上，我们发现倍增也不一定是最优秀的，我们如果再继续细分，分成 $[1,n^{\frac 13}]$ 一段用 LCT 求出，$(n^{\frac 13},n^{\frac 23}]$ 一段在修改时就提前求出它的 $t_i$，询问时暴力跳；剩下的再去暴力倍增。复杂度是 $O(n^{\frac 53}+n^{\frac 43}\cdot\log{n})$，实用意义下更优秀。

E9 codechef BTREE

给一棵树，树上每条边长度为 $1$。现在有 $m$ 次询问，$k$ 个特殊点，每个 特殊点有一个半径，可以覆盖距离它不超过这个半径的所有点。问每天里有多少点被覆盖。$n \le 50000,∑k \le 500000$。

回顾一下单点的情况怎么做。对于每个分治中心预处理下它的分治子树中距离它的距离在 $r$ 以内的点的个数 $h_r$，以及用于容斥的系数 $nh_r$ 表示本子树中到点分治中的父亲的距离在 $r$ 内的点的个数。每次询问直接扫描点到根的链即可。

多点的做法是，对于一个是多个询问点祖先的点 $u$，设询问点在它上的单点询问下的查询分别是 $r_{1,2,\cdots,k}$，那么在多点询问下，此点的贡献就是 $h_{u,\max{r_i}}$。$O((n+\sum{k})\cdot\log{n})$。

（警告：本题此处记载做法是本人 yy 做法，似乎跟题解做法不同，正确性没有验证。）