首页 > 代码库 > POJ2104-- K-th Number（主席树静态区间第k大）
POJ2104-- K-th Number（主席树静态区间第k大）
[转载]一篇还算可以的文章，关于可持久化线段树 http://finaltheory.info/?p=249
无修改的区间第K大
我们先考虑简化的问题：我们要询问整个区间内的第K大。这样我们对值域建线段树，每个节点记录这个区间所包含的元素个数，建树和查询时的区间范围用递归参数传递，然后用二叉查找树的询问方式即可：即如果左边元素个数sum>=K，递归查找左子树第K大，否则递归查找右子树第K – sum大，直到返回叶子的值。
现在我们要回答对于区间[l, r]的第K大询问。如果我们能够得到一个插入原序列中[1, l – 1]元素的线段树，和一颗插入了[1, r]元素的线段树，由于线段树是开在值域上，区间长度是一定的，所以结构也必然是完全相同的，我们可以直接对这两颗线段树进行相减，得到的是相当于插入了区间[l ,r]元素的线段树。注意这里利用到的区间相减性质，实际上是用两颗不同历史版本的线段树进行相减：一颗是插入到第l-1个元素的旧树，一颗是插入到第r元素的新树。
下面是代码
1 #include <cstdio> 2 #include <string> 3 #include <vector> 4 #include <cstdlib> 5 #include <cstring> 6 #include <iostream> 7 #include <algorithm> 8 using namespace std; 9 10 const int maxn = 1e5+10; 11 int A[maxn],B[maxn],mp[maxn],C[maxn]; // A 为原始数组， B为离散化之后的数组 12 int n,m,tot,c[maxn*20],lson[maxn*20],rson[maxn*20]; 13 int build(int l,int r) 14 { 15 int root = tot++; 16 c[root] = 0; 17 if (l != r) 18 { 19 int mid = (l + r) >> 1; 20 lson[root] = build(l,mid); 21 rson[root] = build(mid+1,r); 22 } 23 return root; 24 } 25 int update(int root,int pos,int val) 26 { 27 int newroot = tot++; 28 int tmp = newroot; 29 int l = 1,r = n; 30 c[newroot] = c[root] + val; 31 while (l < r) 32 { 33 int mid = (l + r) >> 1; 34 if (pos <= mid) 35 { 36 rson[newroot] = rson[root]; 37 root = lson[root]; 38 lson[newroot] = tot++; 39 newroot = lson[newroot]; 40 r = mid; 41 } 42 else 43 { 44 lson[newroot] = lson[root]; 45 root = rson[root]; 46 rson[newroot] = tot++; 47 newroot = rson[newroot]; 48 l = mid + 1; 49 } 50 c[newroot] = c[root] + val; 51 } 52 return tmp; 53 } 54 int query(int l_root,int r_root,int k) 55 { 56 int l = 1, r = n; 57 while (l < r) 58 { 59 int mid = (l + r) >> 1; 60 /*if (c[lson[r_root]] - c[lson[l_root]] >= k) 61 { 62 l_root = rson[l_root]; 63 r_root = rson[r_root]; 64 r = mid; 65 } 66 else 67 { 68 k -= (c[rson[r_root]] - c[rson[l_root]]); 69 r_root = lson[r_root]; 70 l_root = lson[l_root]; 71 l = mid + 1; 72 }*/ 73 74 if (c[lson[r_root]] - c[lson[l_root]] >= k) 75 { 76 r = mid; 77 l_root = lson[l_root]; 78 r_root = lson[r_root]; 79 } 80 else 81 { 82 l = mid + 1; 83 k -= c[lson[r_root]] - c[lson[l_root]]; 84 l_root = rson[l_root]; 85 r_root = rson[r_root]; 86 } 87 } 88 return l; 89 } 90 int per_root[maxn]; 91 int main(void) 92 { 93 #ifndef ONLINE_JUDGE 94 freopen("in.txt","r",stdin); 95 #endif 96 while (~scanf ("%d%d",&n,&m)) 97 { 98 tot = 0; 99 for (int i = 1; i <= n; i++)100 {101 scanf ("%d",A+i);102 C[i] = A[i];103 }104 105 sort(A+1,A+n+1);106 n = unique(A + 1, A + n + 1) - A - 1;107 108 for (int i = 1; i <= n; i++)109 {110 B[i] = lower_bound(A+1,A+n+1,C[i]) - A ;111 mp[B[i]] = C[i];112 }113 per_root[0] = build(1,n);114 for (int i = 1; i <= n; i++)115 {116 per_root[i] = update(per_root[i-1],B[i],1);117 }118 for (int i = 0; i < m; i++)119 {120 int l,r,k;121 scanf ("%d%d%d",&l,&r,&k);122 printf("%d\n",mp[query(per_root[l-1],per_root[r], k)]);123 }124 }125 return 0;126 }
POJ2104-- K-th Number（主席树静态区间第k大）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。