P5919. 脉冲后序右侧和

场次：2026年10月14日-非AI方向 · 来源：CodeFun2000 P5919

题目描述

星际探索途中，人类撞见一座年代久远的外星通讯塔。坐标靠一串能量脉冲向外发送。科学家确认，这些互不相同的正整数强度，其实按二叉排序树组织，用来加快检索。

接收端拿到的是一整段脉冲。它记录的是这棵树的后序遍历。

宇宙射线会把这段记录弄乱，于是它未必还能还原成合法的二叉排序树。请完成下面这个核心模块：

• 校验： 判断这段强度能否当作某棵合法二叉排序树的后序遍历。
• 解码： 若能够还原，再求出这座塔「右缘轮廓」上的强度总和。

注： 「右缘轮廓」是从树的右侧望过去，每一层最后映入眼帘的那个结点（也就是该层最靠右的结点）所带的强度。

输出： 能还原时，写下右缘轮廓的强度总和；不能还原时，记成 $-1$。

输入格式

数据来自标准输入。

• 单独一行，若干整数以空格隔开，依次是收到的强度。

数据范围：

• 序列长度 $m$：$1 \le m \le 10000$
• 每个强度 $w$：$1 \le w \le 10^9$，且彼此不重复

输出格式

• 能够还原时，输出一个整数，即右缘轮廓的强度总和。
• 不能还原时，输出 $-1$。

示例

示例 1

输入：

3 8 6 12 15 10

输出：

37

说明：

这段记录末尾的根是 $10$。比 $10$ 小的 $[3, 8, 6]$ 是左子树，比 $10$ 大的 $[12, 15]$ 是右子树。还原后的树是：

• 第 $0$ 层最靠右：$10$
• 第 $1$ 层最靠右：$15$
• 第 $2$ 层最靠右：$12$

右缘轮廓总和：$10 + 15 + 12 = 37$。

示例 2

输入：

3 10 5 8

输出：

-1

说明：

根是 $8$。由最后一个小于 $8$ 的数 $5$ 划出的左段是 $[3, 10, 5]$。其中 $10 > 8$，破坏了左子树必须更小的规则，所以这段记录不能还原，输出 $-1$。

示例 3

输入：

4 7 9

输出：

20

说明：

根是 $9$。$4 < 9$、$7 < 9$，都落在左子树；又有 $4 < 7$，于是 $4$ 挂在 $7$ 的左侧，整棵树一路向左（根 $9$，左孩子 $7$，再往左是 $4$）。从右侧望去，各层可见的强度分别是 $9$、$7$、$4$。

右缘轮廓总和：$9 + 7 + 4 = 20$。

提示

1. 当 $m = 1$ 时，序列里只有一个结点，它自己就是合法的根。
2. 还原这棵树要在 $O(m)$ 内完成，否则极端形态可能超时。建议用单调栈从叶子往根挂边，以免朴素递归分治退化成 $O(m^2)$，也避免递归过深把调用栈撑爆。