CF997E Good Subsegments

一个长度为 $n$ 的排列 $p$ 是一个由 $n$ 个互不相同的整数构成的序列 $p_1, p_2, \ldots, p_n$，其中每个整数都在 $1$ 到 $n$ 之间（$1 \leq p_i \leq n$）。 我们称排列的子区间 $[l, r]$ 是“好”的，如果该区间内的所有数从最小值到最大值之间的每个整数都出现在 $p_l, p_{l+1}, \dots, p_r$ 中。 例如，排列 $[1, 3, 2, 5, 4]$ 的“好”区间有： - $[1, 1]$， - $[1, 3]$， - $[1, 5]$， - $[2, 2]$， - $[2, 3]$， - $[2, 5]$， - $[3, 3]$， - $[4, 4]$， - $[4, 5]$， - $[5, 5]$。 给定一个排列 $p_1, p_2, \ldots, p_n$。 你需要回答 $q$ 个询问，每个询问的形式为：对于排列的某个区间，求该区间内“好”子区间的数量。 换句话说，对于每个询问，你需要计算给定区间 $[l, r]$ 内，所有满足 $l \leq x \leq y \leq r$ 的“好”子区间 $[x, y]$ 的个数。

第一行包含一个整数 $n$（$1 \leq n \leq 120000$），表示排列的元素个数。 第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \ldots, p_n$，用空格分隔（$1 \leq p_i \leq n$）。 第三行包含一个整数 $q$（$1 \leq q \leq 120000$），表示询问的个数。 接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$，用空格分隔（$1 \leq l \leq r \leq n$），表示一次询问。

输出 $q$ 行，第 $i$ 行输出第 $i$ 个询问对应区间内“好”子区间的数量。

由 ChatGPT 4.1 翻译