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

好的，下面是使用分治+主席树的C++实现：

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

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

int n, m;
int a[N], v[N], w[M], h[M], idx;
int cnt[N], root[N], l[M], r[M], sum[M], cntv[M];

void insert(int& u, int l, int r, int x) {
    u = ++ idx;
    sum[u] = sum[h[u - 1]];
    cntv[u] = cntv[h[u - 1]];
    if (l == r) {
        sum[u] ++;
        cntv[u] ++;
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid) {
        insert(l[u], l, mid, x);
    } else {
        insert(r[u], mid + 1, r, x);
    }
    sum[u] = sum[l[u]] + sum[r[u]];
    cntv[u] = cntv[l[u]] + cntv[r[u]];
}

int query(int ul, int ur, int vl, int vr, int l, int r, int k) {
    if (l == r) {
        return l;
    }
    int mid = l + r >> 1;
    int cnt = sum[l[ur]] + sum[l[vl]] - sum[l[ul - 1]] - sum[l[vl - 1]];
    if (cnt >= k) {
        return query(l[ul], l[ur], l[vl], l[vr], l, mid, k);
    } else {
        return query(r[ul], r[ur], r[vl], r[vr], mid + 1, r, k - cnt);
    }
}

void build(int u, int l, int r) {
    for (int i = l; i <= r; i ++ ) {
        insert(root[u], 1, n, a[i]);
    }
    if (l == r) {
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        v[i] = a[i];
    }
    sort(v + 1, v + n + 1);
    int k = unique(v + 1, v + n + 1) - v - 1;
    for (int i = 1; i <= n; i ++ ) {
        a[i] = lower_bound(v + 1, v + k + 1, a[i]) - v;
        w[a[i]] ++;
    }
    build(1, 1, n);
    int q = 0;
    for (int i = 1; i <= m; i ++ ) {
        int l, r, k;
        cin >> l >> r >> k;
        q ++ ;
        l[q] = l, r[q] = r;
        for (int j = 1; j <= k; j ++ ) {
            h[q * k + j] = root[1];
        }
    }
    for (int i = 1; i <= q * k; i ++ ) {
        l[i] = l[(i - 1) / k + 1];
        r[i] = r[(i - 1) / k + 1];
    }
    for (int i = 1; i <= k; i ++ ) {
        cnt[i] = cnt[i - 1] + w[i];
    }
    for (int i = 1; i <= q * k; i ++ ) {
        if (sum[h[i]] - sum[h[i - 1]]) {
            int x = query(h[l[i] - 1], h[r[i]], h[cnt[a[query(h[l[i] - 1], h[r[i]], 1, k, 1, a[query(h[l[i] - 1], h[r[i]], 1, k, 1, k)] - 1)]]], h[cnt[a[query(h[l[i] - 1], h[r[i]], 1, k, 1, k)] - 1] + 1], 1, k, sum[h[i]] - sum[h[i - 1]]);
            cout << v[x] << endl;
        } else {
            cout << -1 << endl;
        }
    }
    return 0;
}

这里的时间复杂度为$O(n\log^2n + m\log n \log k)$，其中$k$为不同数字的数量，空间复杂度为$O(n\log n)$。