笛卡尔树 学习笔记
Visits: 691
碰到好多次了,系统的整理一下。
定义
笛卡尔树跟 Treap 的定义是一样的:
- 二叉树
- 每个节点有一个键值 $(k,w)$。
- $k$ 满足二叉搜索树的性质。
- $w$ 满足二叉堆的性质。
严格意义上讲,Treap 是 $w$ 随机的笛卡尔树。
通常我们可以对一个序列构建笛卡尔树:以下标为 $k$,以元素为 $w$。
这样构建的笛卡尔树的每一个子树都对应着序列的一个区间。
构建
由于对 $k$ 排序后,每次一定是在笛卡尔树的右链上插入一个新的元素。
因此我们可以利用单调栈维护右链。每当一个新节点找到一个位置插入后,把原来那个位置上的子树作为新节点的左儿子即可。
总时间复杂度 $\mathcal O(n)$。
【模板】P5854 【模板】笛卡尔树
const int N = 1e7 + 7;
int n, a[N], s[N], t, l[N], r[N];
ll L, R;
int main() {
rd(n);
for (int i = 1; i <= n; i++) {
rd(a[i]);
int k = t;
while (k && a[s[k]] > a[i]) --k;
if (k) r[s[k]] = i;
if (k < t) l[i] = s[k+1];
s[++k] = i, t = k;
}
for (int i = 1; i <= n; i++) L ^= 1ll * i * (l[i] + 1), R ^= 1ll * i * (r[i] + 1);
print(L, ' '), print(R);
return 0;
}
【例题】P1377 [TJOI2011]树的序
这题实际上是求以元素为 $w$、以下标为 $k$ 的笛卡尔树的先序遍历。
const int N = 1e5 + 7;
int n, a[N], s[N], t, l[N], r[N];
ll L, R;
void dfs(int x) {
if (x) print(x, ' '), dfs(l[x]), dfs(r[x]);
}
int main() {
rd(n);
for (int i = 1, x; i <= n; i++) rd(x), a[x] = i;
for (int i = 1; i <= n; i++) {
int k = t;
while (k && a[s[k]] > a[i]) --k;
if (k) r[s[k]] = i;
if (k < t) l[i] = s[k+1];
s[++k] = i, t = k;
}
dfs(s[1]);
return 0;
}
参考资料
- OI Wiki 笛卡尔树
ql12345
2020年8月20日 上午7:53
“树的序”那道题应该是下标为w,元素为k吧