大家好,欢迎来到IT知识分享网。
Part 1:定义
笛卡尔树是一种每个节点有两个关键字 ( k , w ) (k, w) (k,w),且第一关键字 k k k 构成的树满足二叉搜索树的性质,第二关键字 w w w 构成的树满足堆的性质的树。
(这里有点绕,可以根据图理解一下)
这里放了OI Wiki
上的一棵特殊的笛卡尔树。
在这棵树中,数组下标对应的是元素的第一关键字,数组的值对应的是元素的第二关键字。
不难发现,在上图中,每一棵子树对应的下标是一个连续的区间。
在一般的笛卡尔树中,第一关键字不一定是 1 1 1 到 n n n 的排列,可以为任意的值。
Part 2:性质
一般地,笛卡尔树经第一关键字排序后,一个子树中的节点对应的下标,是一个连续的区间。
下文中的性质及建树,都指按照第一关键字 k k k 排序后的点集。
由于笛卡尔树中元素的第一关键字构成的树满足二叉搜索树的性质,所以在添加元素时,应当将节点添加在当前树的右链上。
如下图:
在图中,所添加的节点要么是根,要么是叶子结点,要么是插在右链的中间。
插在右链中间时,在它下面的子树,会变成该节点的左子树。
即:插入后它下面的那一个节点,会成为它的左儿子。
Part 3:建树
根据排好序的顺序,逐个加点。
因为笛卡尔树满足堆的性质,上面的节点一定大于(或小于)下面的节点。所以,从右链的最下端开始扫描,直到扫到合适的位置(即第二关键字处于当前点两侧的两个点),插入即可。
插入点时,直接将该点压到栈顶。
由于弹出的元素会变成左子树,不会出现在右链中,所以可以证明该做法是正确的。
参考代码:
void insert() {
stack<int> st; // 记录右链节点的编号 int last_pop = 0; // 最后弹出节点的编号 for (int i = 1; i <= n; ++i) {
int sz = st.size(); while (st.size() && nd[st.top()].w > a[i]) last_pop = st.top(), st.pop(); // 本代码中是小根堆,k为 1~n if (st.empty()) {
// 若扫完后栈为空,说明该节点应成为根 root = i; nd[i].lc = last_pop; // 原来的树成为左子树 } else if (st.size() == sz) {
// 没有弹出元素,该点成为叶子 nd[st.top()].rc = i; } else {
// 插在中间 nd[i].lc = last_pop; // 左子结点 nd[st.top()].rc = i; } nd[i].w = a[i]; // w记录第二关键字 st.push(i); // 压进栈 } }
Part 4:例题
Luogu P5854 : 【模板】笛卡尔树
题目描述
给定一个 1 ∼ n 1 \sim n 1∼n 的排列 p p p,构建其笛卡尔树。
即构建一棵二叉树,满足:
- 每个节点的编号满足二叉搜索树的性质。
- 节点 i i i 的权值为 p i p_i pi,每个节点的权值满足小根堆的性质。
输出格式
设 l i , r i l_i,r_i li,ri 分别表示节点 i i i 的左右儿子的编号(若不存在则为 0 0 0)。
一行两个整数,分别表示 xor i = 1 n i × ( l i + 1 ) \operatorname{xor}_{i = 1}^n i \times (l_i + 1) xori=1ni×(li+1) 和 xor i = 1 n i × ( r i + 1 ) \operatorname{xor}_{i = 1}^n i \times (r_i + 1) xori=1ni×(ri+1)。
样例输入
5 4 1 3 2 5
样例输出
19 21
【样例解释】
i i i | l i l_i li | r i r_i ri |
---|---|---|
1 1 1 | 0 0 0 | 0 0 0 |
2 2 2 | 1 1 1 | 4 4 4 |
3 3 3 | 0 0 0 | 0 0 0 |
4 4 4 | 3 3 3 | 5 5 5 |
5 5 5 | 0 0 0 | 0 0 0 |
【数据范围】
对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 1 0 7 1 \le n \le 10^7 1≤n≤107。
计算出每个节点的左右儿子,再统计答案即可。
代码:
#include <bits/stdc++.h> using namespace std; #define int long long // 不开 long long 见祖宗 const int N = 1e7 + 5; inline int read() {
// 快读 int x = 0, f = 1; char c = getchar(); while (!isdigit(c)) {
if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } struct Node {
int lc, rc; int w; }nd[N]; // 记录节点信息 int n; int a[N]; int root = 0; void insert() {
// 同上 stack<int> st; // 记录节点的编号 int last_pop = 0; // 最后弹出的节点的编号 for (int i = 1; i <= n; ++i) {
int sz = st.size(); while (st.size() && nd[st.top()].w > a[i]) last_pop = st.top(), st.pop(); if (st.empty()) {
// 若扫完后栈为空,说明该节点应成为根 root = i; nd[i].lc = last_pop; // 原来的树成为左子树 } else if (st.size() == sz) {
// 没有弹出元素,该点成为叶子 nd[st.top()].rc = i; } else {
// 插在中间 nd[i].lc = last_pop; // 左子结点 nd[st.top()].rc = i; } nd[i].w = a[i]; // w记录第二关键字 st.push(i); // 压进栈 } } signed main() {
cin >> n; for (int i = 1; i <= n; ++i) {
a[i] = read(); } insert(); // 统计左右儿子(构建笛卡尔树) int ans1 = 0, ans2 = 0; for (int i = 1; i <= n; ++i) {
// 统计答案 ans1 ^= i * (nd[i].lc + 1); ans2 ^= i * (nd[i].rc + 1); } cout << ans1 << ' ' << ans2; }
参考文献:
OI Wiki – 笛卡尔树
感谢阅读!
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://haidsoft.com/125998.html