• 2018-01-22
• 0
• 0

# 1、算法描述

• 给定一个序列A[1...n]，现在对该序列能够进行一个操作：Query(left, right, k):表示查询区间[left, right]的第k大树。一共进行m次的查询，要求你尽可能快的实现该操作

```#define MAXN (1<<18)
#define DEEP 20
//sorted用来保存归并树的树体，a为输入序列
int sorted[DEEP][MAXN], a[MAXN];
void build(int deep, int lft, int rht){
if(lft == rht){
sorted[deep][lft] = a[lft];
return ;
}
int mid = (lft + rht) >> 1;
build(deep+1, lft, mid);
build(deep+1, mid+1, rht);
//进行归并
int i = lft, j = mid+1, k = lft;
while(i <= mid && j <= rht){
if(sorted[deep+1][i] <= sorted[deep+1][j])
sorted[deep][k++] = sorted[deep+1][i++];
else sorted[deep][k++] = sorted[deep+1][j++];
}
while(i <= mid) sorted[deep][k++] = sorted[deep+1][i++];
while(j <= rht) sorted[deep][k++] = sorted[deep+1][j++];
}
```

①当y > x时，如果存在这种情况，那么y为区间[left,right]内第k+1大的数，显然y不可能出现在这n1个数。

②当y <= x时，这时候y都满足情况，那么根据①的分析，我们可以发现x是这n1个数中最大的那一个。

```//查询小于key的个数
//[qlft,qrht]为查询区间
//[lft, rht]为归并树上的区间
int query(int deep, int lft, int rht, int qlft, int qrht, int key){
if(qrht < lft || qlft > rht) return 0;
if(qlft <= lft && rht <= qrht)
return std::lower_bound(&sorted[deep][lft], &sorted[deep][rht]+1, key) - &sorted[deep][lft];
int mid = (lft + rht) >> 1;
return query(deep+1, lft, mid, qlft, qrht, key) + query(deep+1, mid+1, rht, qlft, qrht, key);
}
//二分查找在区间[qlft, qrht]上满足是第k大的数
//换而言之，即满足和比key小的有k个数的key
int solve(int n, int qlft, int qrht, int k){
int low = 0, high = n;
while(low+1 < high){
int mid= (low + high) >> 1;
//cnt 为小于 sorted[0][mid]的个数
int cnt = query(0, 0, n-1, qlft, qrht, sorted[0][mid]);
if(cnt <= k) low = mid; //[mid, high)
else high = mid; //[low, mid)
}
return sorted[0][low];
}
```

# 2、时间复杂度

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai