主席树的板子题

题解

方法1. 可持久化线段树（主席树），代码有详细注释
做法:

1. 先把值离散化
2. 在数值上建立线段树，维护每个数值区间中一共有多少个数

问题1：如何求整体第K小数?
答：二分，如果0~mid中有cnt数，cnt>=k,递归左边，如果cnt<k，递归右边，找k−cnt 小的数。时间复杂的logn
问题2：求【1，R】这个区间的第K小数
答：可持久化线段树，从前往后加，刚好加完前R个数时线段树的版本是什么？根节点是ROOT[R],直接搜索根节点
问题3：求【L，R】这个区间有多少个数
答： 用【1，L-1】的个数-【1，R】的个数，同时递归

主席树代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

const int N = 100010, M = 10010;

int n, m;
int a[N];
vector<int> nums;

struct Node {
    int l, r; // 表示左右子节点的下标
    int cnt;  // 当前区间一共有多少个数
} tr[N * 4 + N * 17];

int root[N], idx; // 版本根节点。可用节点的下标

int find(int x) {
    // 求离散化后的值对应原来的是多少
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

int build(int l, int r) {
    // 建树，如果是l==r说明是叶节点，返回节点指针
    // 递归创建左右
    int p = ++idx;
    if (l == r) return p;
    int mid = l + r >> 1;
    tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
    return p;
}

int insert(int p, int l, int r, int x) {
    int q = ++idx;
    tr[q] = tr[p];
    if (l == r) {
        tr[q].cnt++;
        return q;
    }
    int mid = l + r >> 1;
    if (x <= mid)
        tr[q].l = insert(tr[p].l, l, mid, x);
    else
        tr[q].r = insert(tr[p].r, mid + 1, r, x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    return q;
}

int query(int q, int p, int l, int r, int k) {
    // q是上一个版本，p是新的版本
    if (l == r) return r;
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
    int mid = l + r >> 1;
    if (k <= cnt)
        return query(tr[q].l, tr[p].l, l, mid, k);
    else
        return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        nums.push_back(a[i]);
    }
    // 离散化
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    // 建树
    root[0] = build(0, nums.size() - 1);
    for (int i = 1; i <= n; i++)
        root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));

    while (m--) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)]);
    }

    return 0;
}

2. 整体二分+树状数组代码

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010, M = 50010;

int n, m;

struct A {
    int id, x;
}a[N];

struct Q {
    int id;
    int l, r, k;
}q[M];

int f[N], ans[M];

inline bool cmp(const A &p, const A &q) {
    return p.x < q.x;
}

inline int query(int x) {
    int res = 0;
    for (; x; x -= x & -x)
        res += f[x];

    return res;
}

inline void update(int x, int y) {
    for (; x <= n; x += x & -x)
        f[x] += y;
}

void solve(int L, int R, int l, int r) {
    if (l > r)
        return;

    if (L == R) {
        for (int i = l; i <= r; i++)
            ans[q[i].id] = a[L].x;
        return;
    }

    int mid = (L + R) >> 1;

    for (int i = L; i <= mid; i++)
        update(a[i].id, 1);

    int i = l, j = r, t;

    while (i <= j) {
        while (i <= j && q[i].k <= query(q[i].r) - query(q[i].l - 1))
            i++;

        while (i <= j && q[j].k > (t = query(q[j].r) - query(q[j].l - 1))) {
            q[j].k -= t;
            j--;
        }

        if (i < j)
            swap(q[i], q[j]);
    }

    for (int i = L; i <= mid; i++)
        update(a[i].id, -1);

    solve(L, mid, l, j);
    solve(mid + 1, R, i, r);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        a[i].id = i;
        scanf("%d", &a[i].x);
    }

    for (int i = 1; i <= m; i++) {
        q[i].id = i;
        scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k);
    }

    sort(a + 1, a + 1 + n, cmp);

    solve(1, n, 1, m);

    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);

    return 0;
}