POJ 2104 主席树模板题

概述#include <iostream>#include <cstdio>#include <algorithm>int const maxn = 200010;using namespace std;int a[maxn], b[maxn];//第几个版本的根节点编号int root[maxn << 5];int lc[maxn << 5], rc[maxn << 5], sum[

#include <iostream>#include <cstdio>#include <algorithm>int const maxn = 200010;using namespace std;int a[maxn],b[maxn];//第几个版本的根节点编号int root[maxn << 5];int lc[maxn << 5],rc[maxn << 5],sum[maxn << 5];int sz;//节点个数int n,m;int true_n;voID build(int &rt,int l,int r) {    rt = ++sz;    if (l == r) return;    int mID = (l + r) >> 1;    build(lc[rt],l,mID);    build(rc[rt],mID + 1,r);}int update(int ID,int r,int pos) {    int _ID = ++sz;    lc[_ID] = lc[ID],rc[_ID] = rc[ID],sum[_ID] = sum[ID] + 1;    if (l == r) return _ID;    int mID = (r + l) >> 1;    if (pos <= mID)        lc[_ID] = update(lc[ID],mID,pos);    else        rc[_ID] = update(rc[ID],r,pos);    return _ID;}int query(int p,int q,int k) {    if (l == r) return l;    int x = sum[lc[q]] - sum[lc[p]];    int mID = (l + r) >> 1;    if (x >= k)        return query(lc[p],lc[q],k);    else        return query(rc[p],rc[q],k - x);}int main() {    while (~scanf("%d %d",&n,&m)) {        sz = 0;        for (int i = 1; i <= n; i++) {            scanf("%d",&a[i]);            b[i] = a[i];        }        sort(b + 1,b + n + 1);        true_n = unique(b + 1,b + n + 1) - b - 1;        build(root[0],1,true_n);        for (int i = 1; i <= n; i++) {            int pos = lower_bound(b + 1,b + true_n + 1,a[i]) - b;            root[i] = update(root[i - 1],true_n,pos);        }        while (m--) {            int l,k;            scanf("%d %d %d",&l,&r,&k);            cout << b[query(root[l - 1],root[r],k)] << endl;        }    }    return 0;}

总结

以上是内存溢出为你收集整理的POJ 2104 主席树模板题全部内容，希望文章能够帮你解决POJ 2104 主席树模板题所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。