#P18244. Cartesian Trees
Cartesian Trees
Cartesian Trees
题目描述
给定一个 到 的排列 。
对 ,递归定义区间的笛卡尔树 :
- 它是一棵有 个节点的有根二叉树。
- 设 是区间 中最小值的位置,即 。因为 是排列, 唯一。
- 若 ,根的左子树为 ;否则根没有左孩子。
- 若 ,根的右子树为 ;否则根没有右孩子。
给出 个两两不同的区间 ,求这些区间的笛卡尔树中有多少种不同的树形。
两棵树相同,当且仅当它们的根是否有左孩子、是否有右孩子分别一致,存在的左子树递归相同,存在的右子树也递归相同。只比较树形,不比较节点对应的数值;左子树和右子树不能互换。
输入格式
N
A_1 A_2 ... A_N
Q
l_1 r_1
l_2 r_2
...
l_Q r_Q
输出格式
输出一个整数,表示给定区间中不同笛卡尔树的数量。
数据范围
- 所有输入值均为整数。
- 。
- 是 的一个排列。
- 。
- 。
- 任意 均满足 。
样例 1
6
1 4 2 6 3 5
3
1 4
2 5
3 6
2
样例 2
4
1 2 3 4
10
1 1
2 2
3 3
4 4
1 2
2 3
3 4
1 3
2 4
1 4
4
样例 3
10
3 8 4 7 2 5 9 10 1 6
13
5 8
2 6
7 9
3 8
3 5
2 4
4 6
1 9
3 7
6 9
2 10
4 9
3 9
11
样例说明
样例 1 的三棵树如下。图中灰色数字标明原数组中的数值,仅用来帮助对应节点,比较树形时不考虑这些数字。

和 的树形相同, 与它们不同,所以答案为 。