POJ – 2104 K-th Number 主席树基础题

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 8;

//Chairman_Tree
int tot, sz;
int a[MAXN], b[MAXN], root[20*MAXN], ls[20*MAXN], rs[20*MAXN], sum[20*MAXN];

inline void _build(int &o, int l, int r){
    o = ++ tot;
    sum[o] = 0;
    if(l == r) return;
    int mid = (l + r) >> 1;
    _build(ls[o], l, mid);
    _build(rs[o], mid + 1, r);
}

inline void update(int &o, int l, int r, int last, int p){
    o = ++ tot;
    ls[o] = ls[last];
    rs[o] = rs[last];
    sum[o] = sum[last] + 1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(p <= mid) update(ls[o], l, mid, ls[last], p); else update(rs[o], mid + 1, r, rs[last], p); } inline int _query(int ss, int tt, int l, int r, int k){ if(l == r) return l; int mid = (l + r) >> 1;
    int  cnt = sum[ls[tt]] - sum[ls[ss]];
    if(k <= cnt) return _query(ls[ss], ls[tt], l, mid, k); else return _query(rs[ss], rs[tt], mid + 1, r, k - cnt); } int main() { #ifdef LOCAL freopen("a.txt", "r", stdin); //freopen("a.out", "w", stdout); int T = 1; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int n, m, i, ql, qr, x, ind; cin >> n >> m;
    for(i = 1; i <= n; i++){ cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    sz = unique(b + 1, b + n + 1) - (b + 1);
    for(i = 1; i <= n; i++){
        a[i] = lower_bound(b + 1, b + sz + 1, a[i]) - b; //It is based on 1~n..
    }
    tot = 0;
    _build(root[0], 1, sz);
    for(i = 1; i <= n; i++){ update(root[i], 1, sz, root[i-1], a[i]); } while(m--){ cin >> ql >> qr >> x;
        ind = _query(root[ql - 1], root[qr], 1, sz, x);
        cout << b[ind] << "n";
    }


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}