#1290. 【模板】笛卡尔树
【模板】笛卡尔树
题目描述
给定一个 的排列 ,构建其笛卡尔树。
即构建一棵二叉树,满足:
- 每个节点的编号满足二叉搜索树的性质。
- 节点 的权值为 ,每个节点的权值满足小根堆的性质。
输入格式
第一行一个整数 。
第二行一个排列 。
输出格式
设 分别表示节点 的左右儿子的编号(若不存在则为 )。
一行两个整数,分别表示 和 。
样例
5
4 1 3 2 5
19 21
题目来源:洛谷 P5854
给定一个 1∼n 的排列 p,构建其笛卡尔树。
即构建一棵二叉树,满足:
第一行一个整数 n。
第二行一个排列 p1…n。
设 li,ri 分别表示节点 i 的左右儿子的编号(若不存在则为 0)。
一行两个整数,分别表示 xori=1ni×(li+1) 和 xori=1ni×(ri+1)。
5
4 1 3 2 5
19 21
题目来源:洛谷 P5854
By signing up a YSSSN universal account, you can submit code and join discussions in all online judging services provided by us.