【POJ 2104】&HDU 2665 K-th Number

【POJ 2104】&HDU 2665 K-th Number

1.​​题目链接​​。静态区间第k大，主席树的模板题。

2.主席树是个啥玩意，也是刚刚学会（之前都是上模板，现在基本上可以做到手写问题不大），可持久化权值线段树。啥叫可持久化数据结构？就是说如果我又n个操作，现在我在第k个操作，操作完之后，这个数据结构发生了一点改变，现在我想知道第t(t<=k)个操作，这个数据结构是什么样子的，访问它的信息。能够做到这一点的数据结构，就叫做可持久化数据结构。一言以蔽之，就是可以保留历史版本。静态区间第k大就是在数组元素不做改动的情况下，询问[x,y]这个区间第k大的元素。其实这个树状数组+整体二分+离线也是可以做出来，但是主席树可以做到在线回答。先简单的思考这样一个问题，如果询问只有一组该怎么办？（排个序完事），我们考虑一下如何用线段树来解决，如果只有一组询问，我们对整个数组首先离散化一下，然后建立一颗权值线段树，在线段树上二分一下就行了。当询问增加的时候，我们可以增加线段树的，然后完事。但是这显然是不可行的，因为空间不够。所以改用一下前缀和的优点，我们给每个前缀[1,i]（1<=i<=n)建立一颗权值线段树，然后询问的时候，对应相减即可完成，同时对于第i可树和第i+1颗树，只有最右边的那条链不一样，所以空间可重复利用，总体算下来比数组O(n）的空间多了log倍，因为多n条链出来，每条链长度log。所以整体的时空复杂度都是nlogn。

#include#include#include#include#include#includeusing namespace std;typedef long long ll;const int maxn = 1e5 + 5;int T[maxn], L[maxn * 20], R[maxn * 20], sum[maxn * 20];//sz[]为原序列，h[]为离散化后序列int sz[maxn], h[maxn];int n, q, ql, qr, k, tot;void build(int& rt, int l, int r) //建空树{ rt = ++tot; sum[rt] = 0; if (l == r) return; int mid = (l + r) >> 1; build(L[rt], l, mid); build(R[rt], mid + 1, r);}//对所有前缀更新树void update(int& rt, int l, int r, int pre, int x){ rt = ++tot; L[rt] = L[pre]; R[rt] = R[pre]; sum[rt] = sum[pre] + 1; if (l == r) return; int mid = (l + r) >> 1; if (x <= mid) update(L[rt], l, mid, L[pre], x); else update(R[rt], mid + 1, r, R[pre], x);}int query(int s, int e, int l, int r, int k){ if (l == r) return l; int mid = (l + r) >> 1; int res = sum[L[e]] - sum[L[s]]; //左子节点数的个数 if (k <= res) return query(L[s], L[e], l, mid, k); else return query(R[s], R[e], mid + 1, r, k - res);}int main(){ scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) scanf("%d", sz + i), h[i] = sz[i]; sort(h + 1, h + 1 + n); int num = unique(h + 1, h + 1 + n) - h - 1; tot = 0; build(T[0], 1, num); for (int i = 1; i <= n; i++) { //离散化后更新 update(T[i], 1, num, T[i - 1], lower_bound(h + 1, h + 1 + num, sz[i]) - h); } while (q--) { scanf("%d%d%d", &ql, &qr, &k); int ans = query(T[ql - 1], T[qr], 1, num, k); printf("%d\n", h[ans]); } return 0;}

PS：HDU的那道题和这个一样，加个多组就A了

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。