购买网站域名,网站资料素材怎么做,学电商哪个培训学校好,智慧团建网站登录密码昨天的杭电多校联合训练热身赛的一道题#xff0c;求区间的中位数#xff0c;快排会超时#xff0c;划分树的模版题。。 划分树是一种基于线段树的数据结构。主要用于快速求出(在log(n)的时间复杂度内#xff09;序列区间的第k大值 。划分树和归并树都是用线段树作为辅助的…昨天的杭电多校联合训练热身赛的一道题求区间的中位数快排会超时划分树的模版题。。 划分树是一种基于线段树的数据结构。主要用于快速求出(在log(n)的时间复杂度内序列区间的第k大值 。划分树和归并树都是用线段树作为辅助的原理是基于快排 和归并排序 的。划分树的建树过程基本就是模拟快排过程取一个已经排过序的区间中值然后把小于中值的点放左边大于的放右边。并且记录d层第i个数之前包括i小于中值的放在左边的数。具体看下面代码注释。查找其实是关键因为再因查找[l,r]需要到某一点的左右孩子时需要把[l,r]更新。具体分如下几种情况讨论假设要在区间[l,r]中查找第k大元素t为当前节点lchrch为左右孩子leftmid为节点t左边界和中间点。1、sum[r]-sum[l-1]k查找lch[t],区间对应为[ leftsum[l-1] , leftsum[r]-1 ]2、sum[r]-sum[l-1]k,查找rch[t]区间对应为[ mid1l-left-sum[l-1] , mid1r-left-sum[r] ]上面两个关系在纸上可以推出来对着上图更容易理解关系式POJ 2104 划分树模板 http://poj.org/problem?id2104 1 #include iostream 2 #include cstdio 3 #include algorithm 4 using namespace std; 5 #define N 100005 6 int a[N], as[N];//原数组排序后数组 7 int n, m; 8 int sum[20][N];//记录第i层的1~j划分到左子树的元素个数(包括j) 9 int tree[20][N];//记录第i层元素序列10 void build(int c, int l, int r){11 int i, mid (l r) 1, lm mid - l 1, lp l, rp mid 1;12 for (i l; i mid; i){13 if (as[i] as[mid]){14 lm--;//先假设左边的(mid - l 1)个数都等于as[mid],然后把实际上小于as[mid]的减去15 }16 }17 for (i l; i r; i){18 if (i l){19 sum[c][i] 0;//sum[i]表示[l, i]内有多少个数分到左边用DP来维护20 }else{21 sum[c][i] sum[c][i - 1];22 }23 if (tree[c][i] as[mid]){24 if (lm){25 lm--;26 sum[c][i];27 tree[c 1][lp] tree[c][i];28 }else29 tree[c 1][rp] tree[c][i];30 } else if (tree[c][i] as[mid]){31 sum[c][i];32 tree[c 1][lp] tree[c][i];33 } else{34 tree[c 1][rp] tree[c][i];35 }36 }37 if (l r)return;38 build(c 1, l, mid);39 build(c 1, mid 1, r);40 }41 int query(int c, int l, int r, int ql, int qr, int k){42 int s;//[l, ql)内将被划分到左子树的元素数目43 int ss;//[ql, qr]内将被划分到左子树的元素数目44 int mid (l r) 1;45 if (l r){46 return tree[c][l];47 }48 if (l ql){//这里要特殊处理49 s 0;50 ss sum[c][qr];51 }else{52 s sum[c][ql - 1];53 ss sum[c][qr] - s;54 }//假设要在区间[l,r]中查找第k大元素t为当前节点lchrch为左右孩子leftmid为节点t左边界和中间点。55 if (k ss){//sum[r]-sum[l-1]k查找lch[t],区间对应为[ leftsum[l-1], leftsum[r]-1 ]56 return query(c 1, l, mid, l s, l s ss - 1, k);57 }else{//sum[r]-sum[l-1]k,查找rch[t]区间对应为[ mid1l-left-sum[l-1], mid1r-left-sum[r] ]58 return query(c 1, mid 1, r, mid - l 1 ql - s, mid - l 1 qr - s - ss,k - ss);59 }60 }61 int main(){62 int i, j, k;63 while(~scanf(%d%d, n, m)){64 for (i 1; i n; i){65 scanf(%d, a[i]);66 tree[0][i] as[i] a[i];67 }68 sort(as 1, as 1 n);69 build(0, 1, n);70 while(m--){71 scanf(%d%d%d,i,j,k);// i,j分别为区间起始点k为该区间第k大的数。72 printf(%d\n, query(0, 1, n, i, j, k));73 }74 }75 return 0;76 } 转载于:https://www.cnblogs.com/pony1993/archive/2012/07/17/2594544.html
