CF1677E Tokitsukaze and Beautiful Subsegments

时雨拥有一个长度为 $n$ 的排列 $p$。 我们称区间 $[l,r]$ 是“美丽的”，如果存在 $i$ 和 $j$ 满足 $p_i \cdot p_j = \max\{p_l, p_{l+1}, \ldots, p_r\}$，其中 $l \leq i < j \leq r$。 现在时雨有 $q$ 个询问，在第 $i$ 个询问中，她想知道在区间 $[l_i, r_i]$ 内有多少个“美丽的”子区间 $[x, y]$（即 $l_i \leq x \leq y \leq r_i$）。

第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 2 \cdot 10^5$，$1 \leq q \leq 10^6$）——排列 $p$ 的长度和询问的数量。 第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$）——排列 $p$。 接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$）——本次询问的区间 $[l_i, r_i]$。

对于每个询问，输出一个整数，表示在区间 $[l_i, r_i]$ 内“美丽的”子区间的数量。

在第一个样例中，对于第一个询问，有 $2$ 个“美丽的”子区间，分别是 $[1,2]$ 和 $[1,3]$。 由 ChatGPT 4.1 翻译