#1290. 【模板】笛卡尔树

【模板】笛卡尔树

题目描述

给定一个 1∼n1 \sim n 的排列 pp,构建其笛卡尔树。

即构建一棵二叉树,满足:

  1. 每个节点的编号满足二叉搜索树的性质。
  2. 节点 ii 的权值为 pip_i,每个节点的权值满足小根堆的性质。

输入格式

第一行一个整数 nn。

第二行一个排列 p1…np_{1 \dots n}。

输出格式

设 li,ril_i,r_i 分别表示节点 ii 的左右儿子的编号(若不存在则为 00)。

一行两个整数,分别表示 xor⁡i=1ni×(li+1)\operatorname{xor}_{i = 1}^n i \times (l_i + 1) 和 xor⁡i=1ni×(ri+1)\operatorname{xor}_{i = 1}^n i \times (r_i + 1)。

样例

5
4 1 3 2 5
19 21

题目来源:洛谷 P5854