POJ 2104 - K-th Number 划分树初步(不能有相同元素)

网友投稿 560 2022-10-20

POJ 2104 - K-th Number 划分树初步(不能有相同元素)

POJ 2104 - K-th Number 划分树初步(不能有相同元素)

划分树的模型是用来解决一类求一列数的某个区间第k小数的问题.当然也可以通过二分来利用划分树求一个数在某区间里是第几小...跟我的感觉划分树和线段树很多地方挺相似的..

1、划分树的构造

划分树和线段树一样...采用隐性建树...建造的是二叉树...划分树通常使用一个二维数组存储: tree[t][n] ...第一维代表是树的第几层..第二维说明了这层n个数的排列情况..该层n个数虽然连续存储在一起...但可能隐形的分为了好几段.或者说属于不同的点...抽象的说..这些层数列记录的是一个快排的过程..每次快排的基准值是这一段的中位数(中间大的数)....每一层..还未有序的一块就是一个点...可见.第一层..n个数为一个点..第二层1~mid为一个点..mid+1~n为一个点..在这样下去...到了最后面一层..已经成为了一列非递减的数列...而对于每个节点(节点记录的是一排数)..其左右孩子就是这个节点代表的数列段以中位数为基准值后..小于基准值的点以及基准点按照原来的顺序放到排列好..作为其左子树..其他的作为右子树..为了方便后面的统计..构造时同时做一个预处理...记录每一层..到了每个点..其左侧有多少个点划入了左子树...

2、询问过程

询问是找[L,R]区间的第k小数...query函数的形式和线段树一样...那么从第一层进入划分树递归找...区间[L,R]有LtoR个数进入了左子树(建树时做了预处理,直接算出)..若LtoR>=k..那么答案肯定在其左子数上...否则就在其右子树上...但这里和线段树有区别了..线段树在带的时候[L,R]是不变的..这里要调整..因为这里的[L,R]随着层数的深入..是不断的通过映射关系改变的...具体调整方法..参考代码..

Program:

#include#include#include#include#include#include#include#include#include#define ll long long#define eps 1e-5#define oo 1000000007#define pi acos(-1.0)#define MAXN 100005using namespace std; int tree[21][MAXN],num[21][MAXN],sorted[MAXN];void built(int l,int r,int t){ if (l==r) return; int i,x,y,mid=(r+l)>>1; x=l;y=mid+1; //左子树的起点x...右子树的起点y for (i=l;i<=r;i++) { num[t][i]=num[t][i-1]; //预处理每一层每个点其自己以及左侧到左子树的个数 if (tree[t][i]<=sorted[mid]) tree[t+1][x++]=tree[t][i],num[t][i]++; // sorted[mid]为这一段的中位数,放入左子树 else tree[t+1][y++]=tree[t][i]; //放入右子树 } built(l,mid,t+1),built(mid+1,r,t+1); //递归建树}int query(int L,int R,int k,int l,int r,int t){ if (L==R) return tree[t][L]; int ltoL,LtoR,mid=(l+r)>>1; ltoL=num[t][L-1]-num[t][l-1]; //ltoL [l,L]的到左子树点的个数 LtoR=num[t][R]-num[t][L-1]; // LtoR [L,R]的到左子树点的个数 if (LtoR>=k) return query(l+ltoL,l+ltoL+LtoR-1,k,l,mid,t+1); //往左子树去 /* 找其在左子树的映射区间,l+ltoL这个区间到左子树的左边界,l+ltoL+LtoR-1右边界(-1是为了处理边界问题) (l,mid)为(l,r)左子树的左右点. */ int b=L-l-ltoL,bb=R-L+1-LtoR; //求相应的到右子树点的个数 return query(mid+b+1,mid+b+bb,k-LtoR,mid+1,r,t+1); //往右子树去 /* k-LtoR...减去去了左子树的点.. */ }int main(){ int n,m,i; scanf("%d%d",&n,&m); for (i=1;i<=n;i++) scanf("%d",&tree[0][i]),sorted[i]=tree[0][i]; memset(num,0,sizeof(num)); sort(sorted+1,sorted+1+n); built(1,n,0); while (m--) { int l,r,k; scanf("%d%d%d",&l,&r,&k); printf("%d\n",query(l,r,k,1,n,0)); } return 0;}

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

标签：代码 统计
上一篇:pmgo是一个采用Golang编写的Golang应用程序进程管理器
下一篇:HDOJ 1770 - 阅读理解...树形DP
相关文章

 发表评论

暂时没有评论，来抢沙发吧~