【模板】主席树/可持久化线段树(Luogu P3834)

传送门:Luogu P3834 【模板】可持久化线段树 1(主席树)(静态区间第k小)

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define MAX_N 200005
#define MAX_T 8000005

using namespace std;

int n, m, tot = 0;
int a[MAX_N];
int rt[MAX_N];
int L[MAX_T];
int R[MAX_T];
int sum[MAX_T];
vector<int> v;

int getid(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

void build(int o, int &k, int l, int r, int p) {
    k = ++tot;
    sum[k] = sum[o] + 1;
    if (l == r) {
        return;
    }
    int m = (l + r) >> 1;
    if (p <= m) {
        R[k] = R[o];
        build(L[o], L[k], l, m, p);
    } else {
        L[k] = L[o];
        build(R[o], R[k], m + 1, r, p);
    }
}

int getx(int o, int &k, int l, int r, int rk) {
    if (l == r) {
        return l;
    }
    int m = (l + r) >> 1, s = sum[L[k]] - sum[L[o]];
    if (rk <= s) {
        return getx(L[o], L[k], l, m, rk);
    }
    return getx(R[o], R[k], m + 1, r, rk - s);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        v.push_back(a[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int N = v.size();
    for (int i = 1; i <= n; i++) {
        build(rt[i - 1], rt[i], 1, N, getid(a[i]));
    }
    int l, r, k;
    while (m--) {
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", v[getx(rt[l - 1], rt[r], 1, N, k) - 1]);
    }
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注