K-th Number POJ - 2104 | 主席树模板

模板题

题意：
求区间第k小数
分析：
模板题
代码：

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(a) cout << "debug :" << a << endl
#define fi first
#define se second
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
struct node
{
    int l, r, sum;
    node(int a = 0, int b = 0, int c = 0) : l(a), r(b), sum(c){}
}t[maxn << 5];

int root[maxn], tot;
int n, m;
int a[maxn], b[maxn], len;

int build(int l, int r)
{
    int now = tot++;
    t[now].sum = 0;
    if(l == r) return now;
    int mid = l + r >> 1;
    t[now].l = build(l, mid);
    t[now].r = build(mid + 1, r);
    return now;
}

int update(int pre, int l, int r, int v)
{
    int now = tot++;
    t[now] = t[pre], t[now].sum++;
    if(l == r) return now;
    int mid = l + r >> 1;
    if(v <= mid) t[now].l = update(t[pre].l, l, mid, v);
    else t[now].r = update(t[pre].r, mid + 1, r, v);
    return now;
}

int query(int pre, int now, int l, int r, int k)
{
    if(l == r) return l;
    int dif = t[t[now].l].sum - t[t[pre].l].sum;
    int mid = l + r >> 1;
    if(dif >= k) return query(t[pre].l, t[now].l, l, mid, k);
    else return query(t[pre].r, t[now].r, mid + 1, r, k - dif);
}

int getid(int x) { return lower_bound(b + 1, b + 1 + len, x) - b; }

void init() { tot = 0; }

int main()
{
    close();
    while(cin >> n >> m)
    {
        init();
        for(int i = 1; i <= n; i++)
            scanf("%d", a + i), b[i] = a[i];
        sort(b + 1, b + 1 + n);
        len = unique(b + 1, b + 1 + n) - b - 1;
        root[0] = build(1, len);
        for(int i = 1; i <= n; i++)
            root[i] = update(root[i - 1], 1, len, getid(a[i]));
        while(m--)
        {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            int id = query(root[l - 1], root[r], 1, len, k);
            cout << b[id] << endl;
        }  
    }
}