← 返回题目列表

AtCoder · ttpc2024_1_m

M. 笛卡尔树

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

给你一个排列 A = (A_1, A_2, \dots, A_N) of (1, 2, \dots, N).

对于一对整数 l, r (1 \le l \le r \le N),我们定义 笛卡尔树 $$$a$$$ 的 \text{C}(l, r) 如下:

  • \text{C}(l, r) 是一个有根二叉树 r - l + 1 节点。我们将这棵树的根表示为 \mathit{rt}.
  • 让 m 是唯一整数,使得 A_m = \min\lbrace A_l, A_{l+1}, \dots, A_r\rbrace.
  • If l < m,则左子树 \mathit{rt} is \text{C}(l, m-1)。如果 l = m,那么 \mathit{rt} 没有左孩子。
  • If m < r,则右子树 \mathit{rt} is \text{C}(m+1, r)。如果 m = r,那么 \mathit{rt} 没有右孩子。

你被给予 Q 整数对 给出了 (l_1, r_1), (l_2, r_2), \dots, (l_Q, r_Q)。确定其中有多少种不同的笛卡尔树 \text{C}(l_1, r_1), \text{C}(l_2, r_2), \dots, \text{C}(l_Q, r_Q).

两棵笛卡尔树 当且仅当满足以下所有条件时, X 和 Y 才被视为相同:

让根 X be \mathit{rt}_X,以及根 Y be \mathit{rt}_Y.

  • If \mathit{rt}_X 有一个左孩子,那么 \mathit{rt}_Y 也有一个左孩子和左子树 \mathit{rt}_X 和 \mathit{rt}_Y 是相同的笛卡尔树。
  • If \mathit{rt}_X 没有左孩子,那么 \mathit{rt}_Y 也没有左孩子。
  • If \mathit{rt}_X 有一个右孩子,那么 \mathit{rt}_Y 也有一个右孩子和右子树 \mathit{rt}_X 和 \mathit{rt}_Y 是相同的笛卡尔树。
  • If \mathit{rt}_X 没有右孩子,那么 \mathit{rt}_Y 也没有右孩子。

约束

  • 所有输入值均为整数。
  • 1 \le N \le 4 \times 10^5
  • A 是一个排列 (1, 2, \dots, N).
  • 1 \le Q \le 4 \times 10^5
  • 1 \le l_i \le r_i \le N (1 \le i \le Q)
  • (l_i, r_i) \ne (l_j, r_j) (1 \le i < j \le Q)

输入

输入按以下格式给出:

N
A_1 A_2 \ldots A_N
Q
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q

输出

打印答案。


示例输入 1

6
1 4 2 6 3 5
3
1 4
2 5
3 6

示例输出 1

2

\text{C}(1, 4), \text{C}(2, 5), \text{C}(3, 6) 是以下笛卡尔树:

\text{C}(1, 4) 和 \text{C}(3, 6) 是相同的笛卡尔树,而 \text{C}(2, 5) 是与这些不同的笛卡尔树。因此,有 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

示例输出 2

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

示例输出 3

11