题目内容

众所周知，一个长度为$n$，$n$为奇数的数组的中位数是其排序后下标为$\frac{n+1}{2}$的数字。

但小美发现，有些长为奇数n的数组即使不排序，其下标为$\frac{n+1}{2}$的数字依然是其数组中位数，他将满足这样性质的数组成为“好数组"。

问题分析

本题要求我们找到一个排列 p 中的所有“好数组”区间的个数。具体来说，给定一个排列 p 和多个查询，每个查询包含一个长度为奇数的区间 [l, r]，并要求判断区间内的中位数是否满足“好数组”的条件：该区间的中位数恰好是区间的第 (r - l + 1) // 2 + 1 的位置上的数字，并且此中位数在该区间内不需要进行排序后也符合中位数的定义。

“好数组”的定义

“好数组”要求数组的中位数即为该区间的第 (n + 1) / 2 个元素（即中间元素）。例如，若数组的长度为 5，那么第 3 个元素就是中位数。

解题思路