Description
That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i...j] segment, if this segment was sorted?
"
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.
Input
The second line contains n different integer numbers not exceeding 10 9 by their absolute values --- the array for which the answers should be given.
The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).
Output
Sample Input
7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3
Sample Output
5 6 3
Hint
This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.
题目意思：给一个数组。问一个区间内第K大的数。
解题思路：划分树。
划分树是基于高速排序的，首先将原始数组a[]进行排序sorted[]，然后取中位数m，将未排序数组中小于m放在m左边，大于m的放在m右边，并记下原始数列中每一个数左边有多少数小于m，用数组to_left[depth][]表示，这就是建树过程。
重点在于查询过程。设[L,R]为要查询的区间，[l,r]为当前区间，s 表示[L,R]有多少数放到左子树，ss表示[l,L-1]有多少数被放倒左子树。假设s大于等于K，也就是说第K大的数肯定在左子树里。下一步就查询左子树，但这之前先要更新L,R，新的newl=l+ss, newr=newl+s-1。假设s小于k，也就是说第k大的数在右子树里，下一步查询右子树，也要先更新L,R，dd表示[l,L-1]中有多少数被放到右子树，d表示[L,R]有多少数被放到右子树，那么newl = m+1+dd，newr=m+d+dd, 这样查询逐渐缩小查询区间，直到最后L==R 返回最后结果即可。
给出一个大牛的图片样例。
代码：
#include <cstdio> #include <algorithm> #include <iostream> using namespace std; #define maxn 100000+100 int val[30][maxn]; int to_left[30][maxn]; int sorted[maxn]; int n; void build(int l,int r,int d,int rt){ if(l==r) return; int m = (l+r)>>1; int lsame = m-l+1; for(int i=l;i<=r;i++){ if(val[d][i]<sorted[m]) lsame--; } int lpos=l,rpos=m+1,same=0; for(int i=l;i<=r;i++){ if(i==l) to_left[d][i]=0; else to_left[d][i] = to_left[d][i-1]; if(val[d][i]<sorted[m]){ to_left[d][i]++; val[d+1][lpos++] = val[d][i]; }else if(val[d][i]>sorted[m]){ val[d+1][rpos++] = val[d][i]; }else{ if(same<lsame){ same++; to_left[d][i]++; val[d+1][lpos++] = val[d][i]; }else{ val[d+1][rpos++] = val[d][i]; } } } build(l,m,d+1,rt<<1); build(m+1,r,d+1,rt<<1|1); } void print(){ printf("###\n"); for(int i=0;i<10;i++){ for(int j=1;j<=n;j++){ cout << val[i][j]<<" "; } cout << endl; } printf("****\n"); for(int i=0;i<10;i++){ for(int j=1;j<=n;j++){ cout << to_left[i][j]<<" "; } cout << endl; } } int query(int L,int R,int k,int l,int r,int d,int rt){ if(L==R) return val[d][L]; int s,ss; if(L==l){ s = to_left[d][R]; ss = 0; }else{ s = to_left[d][R]-to_left[d][L-1]; ss = to_left[d][L-1]; } int m = (l+r)>>1; if(s>=k){ int newl = l+ss; int newr = newl + s-1; return query(newl,newr,k,l,m,d+1,rt<<1); }else{ int bb = (L-1)-l+1-ss; int b = R-L+1 -s; int newl = m+1+bb; int newr = m+bb+b; // 4 5 1 3 2 (2,5,4) return query(newl,newr,k-s,m+1,r,d+1,rt<<1|1); } } int main(){ int m; scanf("%d %d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&val[0][i]); sorted[i]=val[0][i]; } sort(sorted+1,sorted+n+1); build(1,n,0,1); // print(); while(m--){ int i,j,k; scanf("%d %d %d",&i,&j,&k); printf("%d\n",query(i,j,k,1,n,0,1)); } return 0;}
本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5265373.html 如需转载请自行联系原作者
