HDU 2665 Kth number（划分树入门题，纯套模板）

建树

编辑 建树的过程比较简单，对于区间[l,r]，首先通过对原数组的排序找到这个区间的中位数a[mid]，小于a[mid]的数划入他的左子树[l,mid-1]，大于它的划入右子树[mid,r]。同时，对于第i个数，记录在[l,i]区间内有多少数被划入左子树。最后，对它的左子树区间[l,mid-1]和右子树区间[mid,r]递归的继续建树就可以了。 建树的时候要注意对于被分到同一子树的元素，元素间的相对位置不能改变。

查找

编辑 查找的过程中主要问题就是确定将要查找的区间。这个问题有些麻烦。 先看一下查找过程tree_find.他的定义如下： 查找深度为h，在大区间[st,ed]中找小区间[s,e]中的第k元素。 再看看他是如何工作的。我们的想法是，先判断[s,e]中第k元素在[st,ed]的哪个子树中，然后找出对应的小区间和k，递归的进行查找，直到小区间的s=e为止。 那如何解决这个问题呢？这时候前面记录的进入左子树的元素个数就派上用场了。通过之前的记录可以知道，在区间[st,s-1]中有el[h,s-1]进入左子树，记它为l。同理区间[st,e]中有el[h,e]个数进去左子树，记它为r。所以，我们知道区间小区间[s,e]中有(r-l)个数进入左子树。那么如果(r-l)>=k，那么就在左子树中继续查找，否则就在右子树中继续查找。 接着解决查找的小区间的问题。 如果接下来要查找的是左子树，那么小区间应该是[st+([st,s-1]区间进入左子树的个数),st+([st,e]区间内进入左子树的个数)-1]，即区间[st+l,st+r-1]。显然，这里k不用变。 如果接下来要查找的是右子树，那么小区间应该是[mid+([st,s-1]区间中进入右子树的个数),mid+([st,e]区间进入右子树的个数)-1]。即区间[mid+(s-st-l),mid+(e-st-r)]。显然，这里k要减去区间里已经进入左子树的个数，即k变为k-(r-l)。 于是递归继续查找直到s=e即可。

#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> using namespace std; const int MAXN=100010; int tree[30][MAXN];//表示每层每个位置的值 int sorted[MAXN];//已经排序的数 int toleft[30][MAXN];//toleft[p][i]表示第i层从1到i有多少个数分入左边 void build(int l,int r,int dep) { if(l==r)return; int mid=(l+r)>>1; int same=mid-l+1;//表示等于中间值而且被分入左边的个数 for(int i=l;i<=r;i++) if(tree[dep][i]<sorted[mid]) same--; int lpos=l; int rpos=mid+1; for(int i=l;i<=r;i++) { if(tree[dep][i]<sorted[mid])//比中间的数小，分入左边 tree[dep+1][lpos++]=tree[dep][i]; else if(tree[dep][i]==sorted[mid]&&same>0) { tree[dep+1][lpos++]=tree[dep][i]; same--; } else //比中间值大分入右边 tree[dep+1][rpos++]=tree[dep][i]; toleft[dep][i]=toleft[dep][l-1]+lpos-l;//从1到i放左边的个数 } build(l,mid,dep+1); build(mid+1,r,dep+1); } //查询区间第k大的数，[L,R]是大区间，[l,r]是要查询的小区间 int query(int L,int R,int l,int r,int dep,int k) { if(l==r)return tree[dep][l]; int mid=(L+R)>>1; int cnt=toleft[dep][r]-toleft[dep][l-1];//[l,r]中位于左边的个数 if(cnt>=k) { //L+要查询的区间前被放在左边的个数 int newl=L+toleft[dep][l-1]-toleft[dep][L-1]; //左端点加上查询区间会被放在左边的个数 int newr=newl+cnt-1; return query(L,mid,newl,newr,dep+1,k); } else { int newr=r+toleft[dep][R]-toleft[dep][r]; int newl=newr-(r-l-cnt); return query(mid+1,R,newl,newr,dep+1,k-cnt); } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int T; int n,m; int s,t,k; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(tree,0,sizeof(tree));//这个必须 for(int i=1;i<=n;i++)//从1开始 { scanf("%d",&tree[0][i]); sorted[i]=tree[0][i]; } sort(sorted+1,sorted+n+1); build(1,n,0); while(m--) { scanf("%d%d%d",&s,&t,&k); printf("%d\n",query(1,n,s,t,0,k)); } } return 0; }