G. 【普及】统计稳定子数组的数目

传统题

100ms

32MiB

【普及】统计稳定子数组的数目

给你一个长度为 $n$ 的正整数数组 $a$

如果 $a$ 的一个 连续子数组 中没有逆序对，即不存在满足 $i < j$ 且 $a[i] > a[j]$ 的下标对，则该子数组被称为稳定子数组

现在有 $q$ 个询问，每个询问需要统计完全包含在 $a[l_i, \cdots r_i]$ 内的 稳定子数组 的数量

第一行包含 $2$ 个正整数 $n, q(1 \le n, q \le 10^5)$ ，表示数组 $a$ 的长度和询问个数

第二行包含 $n$ 个正整数，表示数组 $a$

接下来 $q$ 行，每行包含 $2$ 个数 $l_i, r_i(0 \le l_i, r_i \le n - 1)$

输出 $1$ 行包含 $q$ 个数，表示每个询问的答案

2 3 4

3 1

【样例 1 解释】

对于询问 $[l_i, r_i] = [0, 1]$ $[l_{i}, r_{i}] = [0, 1]$ ，子数组为 $[3, 1]$ $[3, 1]$
- 稳定子数组包括 $[3]$ 和 $[1]$ ，稳定子数组的总数为 $2$
- 子数组 $[3, 1]$ 包含逆序对
对于询问 $[l_i, r_i] = [1, 2]$ $[l_{i}, r_{i}] = [1, 2]$ ，子数组为 $[1, 2]$ $[1, 2]$
- 稳定子数组包括 $[1], [2], [1, 2]$ ，稳定子数组的总数为 $3$
对于询问 $[l_i, r_i] = [0, 2]$ $[l_{i}, r_{i}] = [0, 2]$ ，子数组为 $[3, 1, 2]$ $[3, 1, 2]$
- 稳定子数组包括 $[3], [1], [2], [1, 2]$ ，稳定子数组的总数为 $4$

【样例 2 解释】

对于询问 $[l_i, r_i] = [0, 1]$ $[l_{i}, r_{i}] = [0, 1]$ ，子数组为 $[2, 2]$ $[2, 2]$
- 稳定子数组包括 $[2], [2], [2, 2]$ ，稳定子数组的总数为 $3$
对于询问 $[l_i, r_i] = [0, 0]$ $[l_{i}, r_{i}] = [0, 0]$ ，子数组为 $[2]$ $[2]$
- 稳定子数组包括 $[2]$ ，稳定子数组的总数为 $1$

【数据范围】

请思考后再点击查看提示