给定一个长度为n的数组，求m次l，r区间内的中位数，用c++解决

在C++中，我们可以使用优先队列（`priority_queue`）和快速选择算法（QuickSelect）来高效地计算给定数组中每个区间的中位数。这个算法的时间复杂度通常能达到O(n)，对于每个查询`l, r`都是如此。

首先，我们需要对整个数组进行排序。然后，针对每个区间`[l, r]`，我们可以在O(log m)时间内找到第`(r-l+1)/2`小（如果(r-l)是奇数）或第`(r-l+2)/2`小（如果(r-l)是偶数）的元素，这是由于快速选择算法的特性。这里我们使用两个堆来辅助操作：

1. 初始化两个优先队列，一个大顶堆（`greater<int>`），用于存储小于中间值的元素；另一个小顶堆（`greater_equal<int>`），用于存储大于等于中间值的元素。
2. 对于每个区间 `[l, r]`，从数组中取出元素并与堆进行交互，维护堆的性质：
- 如果元素位于中间位置，直接返回该元素；
- 如果元素比当前中间值小，入大顶堆；
- 如果元素比当前中间值大，入小顶堆，并调整堆的大小，以保持堆的正确结构。
3. 当处理完所有元素后，如果`l`是奇数，中位数就是堆顶的大顶堆元素；如果是偶数，则中位数是堆顶元素和倒数第二个元素的平均值。

以下是简单的伪代码概述：

void quick_select(vector<int>& arr, int l, int r, int k) {
    // ... 实现快速选择算法
}

int find_median(vector<int>& nums, int start, int end, int target) {
    if (start == end)
        return nums[start];

    // ... 使用快速选择找到第k小的元素

    priority_queue<int, vector<int>, greater<int>> max_heap;
    priority_queue<int, vector<int>, greater_equal<int>> min_heap;

    // ... 使用两个堆来找到目标中位数
}

int median_query(vector<int>& nums, vector<pair<int, int>>& queries) {
    sort(nums.begin(), nums.end());
    for (auto [l, r] : queries) {
        cout << find_median(nums, l, r, (r-l+1)/2) << endl;
    }
}