洛谷 - P3834 主席树

传送门：洛谷 - P3834

题目描述

求静态区间第K小

输入描述

第一行包含两个正整数 $n$,$m$，分别表示序列的长度和查询的个数
第二行包含 $n$ 个整数，表示这个序列各项的数字
接下来 $m$ 行每行包含三个整数 $l$, $r$, $k$ 表示查询区间 $[l, r]$ 内的第 $k$ 小值。

输出描述

输出包含 $m$ 行，每行一个整数，依次表示每一次查询的结果

思路分析

对于每一个前缀建立一颗权值线段树，类似于前缀和，计算的时候$R-(l-1)$就是答案了，用主席树来减少空间

样例输入

5 5
25957 6405 15770 26287 26465 
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

样例输出

6405
15770
26287
25957
26287

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define fun function
#define ll long long
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;

struct node {
    int l, r, sum;
} tree[N * 40];

int cnt, root[N], a[N];
vector<int> v;

void ins(int l, int r, int pre, int &now, int pos) {
    tree[++cnt] = tree[pre]; //复制前驱
    now = cnt;
    tree[now].sum++;
    if (l == r)
        return;
    int mid = l + r >> 1;
    if (pos <= mid)
        ins(l, mid, tree[pre].l, tree[now].l, pos);
    else
        ins(mid + 1, r, tree[pre].r, tree[now].r, pos);

}

int query(int l, int r, int L, int R, int k) {
    if (l == r)
        return l;
    int mid = l + r >> 1;
    int temp = tree[tree[R].l].sum - tree[tree[L].l].sum;
    if (k <= temp)
        return query(l, mid, tree[L].l , tree[R].l, k);
    else
        return query(mid + 1, r, tree[L].r, tree[R].r, k - temp); //减去左子树的大小
}

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

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        v.push_back(a[i]);
    }
    sort(all(v));
    v.erase(unique(all(v)), v.end());

    int tot = v.size();
    for (int i = 1; i <= n; i++)
        ins(1, tot, root[i - 1], root[i], getid(a[i]));
    while (m--) {
        int l, r, k;
        cin >> l >> r >> k;
        cout << v[query(1, tot, root[l - 1], root[r], k) - 1] << endl;
    }


    return 0;
}