首页 > 代码库 > POJ 2104 K-th Number 主席树 区间第K大
POJ 2104 K-th Number 主席树 区间第K大
今天第一次接触可持久化数据结构，还是有必要总结一下的。
首先对于查找第k大的问题，先搞清楚怎么样通过利用N颗线段树来求解。如果是求全局第K大，那么可以把数字的值作为位置插入线段树，然后通过区间和+二分来找到第k个位置。因为是通过区间和来找第k大的，显然是满足前缀和性质的，所以查询l,r区间的第k打，就直接根据1-l - 1,1-r两个区间建立两颗线段树，然后通过节点依次相减来求得第k大值。所以这样子解需要的内存空间是n*n*logn的（不需要管数的范围，范围再大也可以通过离散化缩小到n）。
但是注意到每一棵树相对于前一颗只有一个节点被修改了，最多只有logn个节点变化，所以只存储修改过的节点，然后用指针指向原来的的不变的节点就好。
第一次写，实现起来感觉还是有点蛋疼的。不过也不长=。=
#include <cstdio>#include <cstring>#include <algorithm>#include <vector>using namespace std;const int maxn = 100000 + 10;const int maxm = maxn * 30;int lc[maxm], rc[maxm], sumv[maxm], cnt;int root[maxn], n, q, a[maxn];vector<int> vnum;void init() { cnt = 1; root[0] = 0;}void build(int rt, int l, int r) { sumv[rt] = 0; if (l == r) return; int mid = (l + r) >> 1; lc[rt] = cnt++; rc[rt] = cnt++; build(lc[rt], l, mid); build(rc[rt], mid + 1, r);}void update1(int rt, int prt, int l, int r, int pos, int val) { int mid = (l + r) >> 1; if (l == r) return; if (pos <= mid) { int newrt = cnt++; lc[rt] = newrt; sumv[newrt] = sumv[lc[prt]] + val; rc[rt] = rc[prt]; update1(newrt, lc[prt], l, mid, pos, val); } else { int newrt = cnt++; rc[rt] = newrt; sumv[newrt] = sumv[rc[prt]] + val; lc[rt] = lc[prt]; update1(newrt, rc[prt], mid + 1, r, pos, val); }}void update(int rt, int pos, int val) { root[rt] = cnt++; sumv[root[rt]] = sumv[root[rt - 1]] + val; update1(root[rt], root[rt - 1], 1, n, pos, val);}int query(int lroot, int rroot, int l, int r, int k) { int mid = (l + r) >> 1, nowsum = sumv[lc[rroot]] - sumv[lc[lroot]]; if (l == r) return vnum[l - 1]; if (nowsum >= k) return query(lc[lroot], lc[rroot], l, mid, k); else return query(rc[lroot], rc[rroot], mid + 1, r, k - nowsum);}int getid(int val) { return lower_bound(vnum.begin(), vnum.end(), val) - vnum.begin() + 1;}int main() { while (scanf("%d%d", &n, &q) != EOF) { init(); vnum.clear(); build(root[0], 1, n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); vnum.push_back(a[i]); } sort(vnum.begin(), vnum.end()); vnum.erase(unique(vnum.begin(), vnum.end()), vnum.end()); for (int i = 1; i <= n; i++) { update(i, getid(a[i]), 1); } while (q--) { int l, r, k; scanf("%d%d%d", &l, &r, &k); int ret = query(root[l - 1], root[r], 1, n, k); printf("%d\n", ret); } } return 0;}
POJ 2104 K-th Number 主席树 区间第K大
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。