NOIP模板复习 _ 主席树 – [模板]

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210000;
const int INF = 1e9;
int root[N], ls[N<<5], rs[N<<5], t[N<<5], cnt;
void insert(int l, int r, int p, int &q, int x) {
    q = ++cnt; t[q] = t[p]+1;
    if(l == r) return;
    int mid = (l+r) >> 1;
    if(x <= mid) rs[q] = rs[p], insert(l, mid, ls[p], ls[q], x);
    else ls[q] = ls[p], insert(mid+1, r, rs[p], rs[q], x);
}
int query(int l, int r, int p, int q, int k) {
    if(l == r) return l;
    int sizl = t[ls[q]]-t[ls[p]];
    int mid = (l+r) >> 1;
    if(sizl >= k) return query(l, mid, ls[p], ls[q], k);
    else return query(mid+1, r, rs[p], rs[q], k-sizl);
}
int main() {
    int n, Q; scanf("%d%d", &n, &Q);
    for(int i = 1; i <= n; i ++ ) {
        int x; scanf("%d", &x);
        insert(-INF, INF, root[i-1], root[i], x);
    }
    while(Q -- ) {
        int l, r, k; scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", query(-INF, INF, root[l-1], root[r], k));
    }
}

发表评论

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