POJ K-th Number

时间:2023-03-08 15:39:28

POJ K-th Number

POJ K-th Number

【题解】

数据结构采用线段树。通过将数组的每一段归并排序来建树。将数组排序来实现离散化。

时间复杂度分析:建树的过程就是归并排序,其时间复杂度为O(nlog(n))。查询时:二分查找第k小元素的复杂度为O(log(n)),访问一个节点的复杂度为O(log(n))。因此,查询一次的复杂度为O((logn)^3),总复杂度为O(m(logn)^3)。

空间复杂度:O(n)。

【代码】

 #include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MID(x, y) ((x + y) >> 1)
#define lson(x) (x << 1)
#define rson(x) ((x << 1) | 1) using namespace std; const int maxn = ;
const int maxm = ; int a[maxn << ];
vector<int> tree[maxm << ]; void build(int root, int L, int R)
{
if (L == R) {
tree[root].push_back(a[L]);
return;
}
build(lson(root), L, MID(L, R)), build(rson(root), MID(L, R) + , R);
tree[root].resize(R - L + );
merge(tree[lson(root)].begin(), tree[lson(root)].end(), tree[rson(root)].begin(),
tree[rson(root)].end(), tree[root].begin());
} int query(int root, int l, int r, int L, int R, int x)
{
if (r < L || l > R)return ;
if (L <= l && r <= R) {
return upper_bound(tree[root].begin(), tree[root].end(), x) - tree[root].begin();
}
else {
int re1 = , re2 = ;
re1 = query(lson(root), l, MID(l, r), L, R, x);
re2 = query(rson(root), MID(l, r) + , r, L, R, x);
return re1 + re2;
}
} int main()
{
int array_size, quest_n, i = , j, k, l, r, mid, ans;
scanf("%d %d", &array_size, &quest_n);
for (i = ; i <= array_size; i++) scanf("%d", &a[i]);
build(, , array_size);
sort(a + , a + array_size + );
while (quest_n--) {
scanf("%d %d %d", &i, &j, &k);
l = , r = array_size;
mid = , ans = ;
while (l <= r) {
mid = MID(l, r);
if (query(, , array_size, i, j, a[mid]) >= k) {
ans = mid;
r = mid - ;
}
else l = mid + ;
}
printf("%d\n", a[ans]);
}
return ;
}