本文主要是介绍归并树 第K大值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*1.O(n*(logn)^2)
2.树的节点node从1开始（方便位运算）
3.树的层数h从0开始（节约空间）
4.数组a的下标从1开始
5.我们在queryVal中二分的是[1,n]整个区间，而不是[l,r]区间，这似乎是不正确的。因为假如[l,r]区间
中的值为[2,10,22,23]，我们要求第3大的值，如果二分到的值是11，他的在[l,r]中的rank为3，这不就错了么？
所以有一点一定要注意:【数组a中的值不重能复】：queryRank中二分取极大，queryVal中二分取极小，
两个条件限制下，就可保证22被选到。
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>#define MID(l,r) ((l+r)>>1)
#define L(u) (u<<1)
#define R(u) (u<<1|1)
using namespace std;const int MAXN = 100010;
struct MerNode {int l, r;};
MerNode node[MAXN<<2];
int seg[20][MAXN], a[MAXN], n;void build(int u, int l, int r, int h)
{node[u].l = l;node[u].r = r;if(l == r){seg[h][l] = a[l];return ;}int mid = MID(l, r);build(L(u), l, mid, h+1);build(R(u), mid+1, r, h+1);int k = l, i = l, j = mid+1;while(i <= mid && j <= r){if(seg[h+1][i] < seg[h+1][j] )seg[h][k++] = seg[h+1][i++];elseseg[h][k++] = seg[h+1][j++];}while(i <= mid) seg[h][k++] = seg[h+1][i++];while(j <= r) seg[h][k++] = seg[h+1][j++];
}//查询区间[l,r]中小于等于val的个数，即val的rank
//更改内部的二分函数可以求<,<=,>,>=各种情况
int queryRank(int u, int l, int r, int h, int val)
{if(node[u].l == l && node[u].r == r){int tl = node[u].l, tr = node[u].r;while(tl < tr){int mid = MID(tl, tr);if(seg[h][mid] < val) tl = mid + 1;else tr = mid;}if(seg[h][tl] <= val)return tl - node[u].l + 1;elsereturn tl - node[u].l;}int cnt = 0;int mid = MID(node[u].l, node[u].r);if(r <= mid)cnt = queryRank(L(u), l, r, h+1, val);else if(l > mid)cnt = queryRank(R(u), l, r, h+1, val);elsecnt = queryRank(L(u), l, mid, h + 1, val) + queryRank(R(u), mid + 1, r, h + 1, val);return cnt;
}//查询[l,r]第k大的数的值
//seg[0][]已经排好序
int queryVal(int s, int t, int k)
{int l = 1, r = n;while(l < r){int mid = MID(l, r);if(queryRank(1, s, t, 0, seg[0][mid]) < k)l = mid + 1;elser = mid;}return seg[0][l];
}int main()
{int m, s, t, k;while(scanf("%d%d",&n,&m) != EOF){for(int i = 1; i <= n; i++)scanf("%d",&a[i]);build(1, 1, n, 0);while( m-- ){scanf("%d%d%d",&s,&t,&k);printf("%d\n",queryVal(s,t,k));}}return 0;
}
这篇关于归并树 第K大值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
