给定一个长为n 的序列a 。 有m 次询问，求区间[l,r] 中出现次数第k 小的数，若有多个则输出最小的。 出现次数第k 小的数指恰有k-1 个数的出现次数严格小于该数。c++实现

好的，这道题可以使用桶排序或者堆来解决，下面分别介绍两种解法。

1.使用桶排序

我们可以使用一个桶来记录每个数字出现的次数，然后再使用一个桶来记录出现次数的数量，最后从小到大遍历出现次数的桶，直到找到第k个出现次数不为0的桶，此时该桶的编号就是第k小的数字。如果有多个数字出现次数相同，我们可以在第k个桶中遍历查找最小的数字即可。

具体实现时，我们可以先将所有数字存入桶中，然后遍历桶，统计出现次数的数量，最后再次遍历桶，找到第k个出现次数不为0的桶，输出该桶中最小的数字即可。

下面是使用C++实现的代码：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N], cnt[N], cntv[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        cnt[a[i]] ++;
    }
    int k = unique(a + 1, a + n + 1) - a - 1;
    for (int i = 1; i <= k; i ++ ) {
        cntv[cnt[i]] ++;
    }
    int ans = 0;
    for (int i = 1; i <= k; i ++ ) {
        if (cntv[i]) {
            ans ++;
            if (ans == m) {
                for (int j = 1; j <= n; j ++ ) {
                    if (a[j] <= i && cnt[a[j]] == i) {
                        cout << a[j] << endl;
                        break;
                    }
                }
                break;
            }
        }
    }
    return 0;
}

时间复杂度为$O(n+m)$，空间复杂度为$O(n)$。

2.使用堆

我们可以使用一个小根堆来存储数字和出现次数的信息，每次弹出最小的元素，直到弹出第k个元素，此时堆顶的数字就是第k小的数字。为了避免重复，我们可以将数字和下标存入堆中，然后按照下标从小到大排序。

具体实现时，我们可以先将所有数字存入堆中，然后按照下标从小到大排序，从堆中弹出前k-1个元素，此时堆顶的数字就是第k小的数字。

下面是使用C++实现的代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

int n, m;
int a[N], cnt[N];
priority_queue<PII, vector<PII>, greater<PII>> heap;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        cnt[a[i]] ++;
    }
    for (int i = 1; i <= n; i ++ ) {
        if (cnt[a[i]]) {
            heap.push({i, a[i]});
            cnt[a[i]] = 0;
        }
    }
    sort(a + 1, a + n + 1);
    int l = 1, r = n;
    while (l <= r && heap.size() < m) {
        if (a[l] == heap.top().second) {
            heap.pop();
        }
        l ++;
    }
    cout << heap.top().second << endl;
    return 0;
}

时间复杂度为$O(n\log n)$，空间复杂度为$O(n)$。