#P18244. Cartesian Trees

Cartesian Trees

Cartesian Trees

题目描述

给定一个 11 到 NN 的排列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N)。

对 1≤l≤r≤N1\le l\le r\le N,递归定义区间的笛卡尔树 C(l,r)C(l,r):

  • 它是一棵有 r−l+1r-l+1 个节点的有根二叉树。
  • 设 mm 是区间 [l,r][l,r] 中最小值的位置,即 Am=min⁡(Al,…,Ar)A_m=\min(A_l,\ldots,A_r)。因为 AA 是排列,mm 唯一。
  • 若 l<ml<m,根的左子树为 C(l,m−1)C(l,m-1);否则根没有左孩子。
  • 若 m<rm<r,根的右子树为 C(m+1,r)C(m+1,r);否则根没有右孩子。

给出 QQ 个两两不同的区间 (l1,r1),…,(lQ,rQ)(l_1,r_1),\ldots,(l_Q,r_Q),求这些区间的笛卡尔树中有多少种不同的树形。

两棵树相同,当且仅当它们的根是否有左孩子、是否有右孩子分别一致,存在的左子树递归相同,存在的右子树也递归相同。只比较树形,不比较节点对应的数值;左子树和右子树不能互换。

输入格式

N
A_1 A_2 ... A_N
Q
l_1 r_1
l_2 r_2
...
l_Q r_Q

输出格式

输出一个整数,表示给定区间中不同笛卡尔树的数量。

数据范围

  • 所有输入值均为整数。
  • 1≤N≤4×1051\le N\le 4\times10^5。
  • AA 是 1,2,…,N1,2,\ldots,N 的一个排列。
  • 1≤Q≤4×1051\le Q\le 4\times10^5。
  • 1≤li≤ri≤N1\le l_i\le r_i\le N。
  • 任意 i≠ji\ne j 均满足 (li,ri)≠(lj,rj)(l_i,r_i)\ne(l_j,r_j)。

样例 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 的三棵树如下。图中灰色数字标明原数组中的数值,仅用来帮助对应节点,比较树形时不考虑这些数字。

样例1的三棵笛卡尔树

C(1,4)C(1,4) 和 C(3,6)C(3,6) 的树形相同,C(2,5)C(2,5) 与它们不同,所以答案为 22。