http://acm.hdu.edu.cn/showproblem.php?pid=2665

?[ poj 2104?2761 ]? 改變一下輸入就可以過

http://poj.org/problem?id=2104

http://poj.org/problem?id=2761

Kth number

Time Limit: 15000/5000 MS (Java/Others)??? Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3266??? Accepted Submission(s): 1090

Problem Description Give you a sequence and ask you the kth big number of a inteval. Input The first line is the number of the test cases. For each test case, the first line contain two integer n and m (n, m <= 100000), indicates the number of integers in the sequence and the number of the quaere.
The second line contains n integers, describe the sequence. Each of following m lines contains three integers s, t, k. [s, t] indicates the interval and k indicates the kth big number in interval [s, t] Output For each test case, output m lines. Each line contains the kth big number. Sample Input 1 10 1 1 4 2 3 5 6 7 8 9 0 1 3 2 Sample Output 2 Source HDU男生專場公開賽——趕在女生之前先過節（From WHU） 思路： 劃分樹模板：

劃分樹是一種基于線段樹的數據結構。主要用于快速求出(在log(n)的時間復雜度內）序列區間的第k大值?。

劃分樹和歸并樹都是用線段樹作為輔助的，原理是基于快排?和歸并排序?的。

劃分樹的建樹過程基本就是模擬快排過程，取一個已經排過序的區間中值，然后把小于中值的點放左邊，大于的放右邊。并且記錄d層第i個數之前（包括i）小于中值的放在左邊的數。具體看下面代碼注釋。

?

查找其實是關鍵，因為再因查找[l,r]需要到某一點的左右孩子時需要把[l,r]更新。具體分如下幾種情況討論： 假設要在區間[l,r]中查找第k大元素，t為當前節點，lch，rch為左右孩子，left，mid為節點t左邊界和中間點。

1、sum[r]-sum[l-1]>=k，查找lch[t],區間對應為[ left+sum[l-1] , left+sum[r]-1 ]

2、sum[r]-sum[l-1]<k,查找rch[t]，區間對應為[ mid+1+l-left-sum[l-1] , mid+1+r-left-sum[r] ]

上面兩個關系在紙上可以推出來，對著上圖更容易理解關系式；

講解轉自：http://www.cnblogs.com/pony1993/archive/2012/07/17/2594544.html

?

AC代碼：

1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<string.h> 5 6 using namespace std; 7 8 #define N 100010 9 10 int sorted[N]; //排序完的數組 11 int toleft[30][N]; //toleft[i][j]表示第i層從1到k有多少個數分入左邊 12 int tree[30][N]; //表示每層每個位置的值 13 14 void buildingTree(int l,int r,int dep) 15 { 16 if(l==r) return; 17 int mid = (l+r)>>1; 18 int i,sum = mid-l+1; //表示等于中間值而且被分入左邊的個數 19 for(i=l;i<=r;i++) 20 { 21 if(tree[dep][i]<sorted[mid]) sum--; 22 } 23 int lpos=l; 24 int rpos=mid+1; 25 for(i=l;i<=r;i++) 26 { 27 if(tree[dep][i]<sorted[mid]) //比中間的數小，分入左邊 28 { 29 tree[dep+1][lpos++]=tree[dep][i]; 30 } 31 else if(tree[dep][i]==sorted[mid]&&sum>0) //等于中間的數值，分入左邊，直到sum==0后分到右邊 32 { 33 tree[dep+1][lpos++]=tree[dep][i]; 34 sum--; 35 } 36 else //右邊 37 { 38 tree[dep+1][rpos++]=tree[dep][i]; 39 } 40 toleft[dep][i] = toleft[dep][l-1] + lpos - l; //從1到i放左邊的個數 41 } 42 buildingTree(l,mid,dep+1); 43 buildingTree(mid+1,r,dep+1); 44 } 45 46 //查詢區間第k大的數，[L,R]是大區間，[l,r]是要查詢的小區間 47 int queryTree(int L,int R,int l,int r,int dep,int k) 48 { 49 if(l==r) return tree[dep][l]; 50 int mid = (L+R)>>1; 51 int cnt = toleft[dep][r] - toleft[dep][l-1]; //[l,r]中位于左邊的個數 52 if(cnt>=k) 53 { 54 int newl = L + toleft[dep][l-1] - toleft[dep][L-1]; //L+要查詢的區間前被放在左邊的個數 55 int newr = newl + cnt - 1; //左端點加上查詢區間會被放在左邊的個數 56 return queryTree(L,mid,newl,newr,dep+1,k); 57 } 58 else 59 { 60 int newr = r + toleft[dep][R] - toleft[dep][r]; 61 int newl = newr - (r - l - cnt); 62 return queryTree(mid+1,R,newl,newr,dep+1,k-cnt); 63 } 64 } 65 66 67 int main() 68 { 69 int t; 70 scanf("%d",&t); 71 while(t--) 72 { 73 int n,m,i; 74 scanf("%d%d",&n,&m); 75 for(i=1;i<=n;i++) 76 { 77 scanf("%d",&tree[0][i]); 78 sorted[i] = tree[0][i]; 79 } 80 sort(sorted+1,sorted+1+n); 81 buildingTree(1,n,0); 82 while(m--) 83 { 84 int s,t,k; 85 scanf("%d%d%d",&s,&t,&k); 86 printf("%d\n",queryTree(1,n,s,t,0,k)); 87 } 88 } 89 return 0; 90 }

?

?

?

轉載于:https://www.cnblogs.com/crazyapple/p/3223954.html

總結

以上是生活随笔為你收集整理的hdu 2665 Kth number(划分树模板)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。