【题解】
数据结构采用线段树。通过将数组的每一段归并排序来建树。将数组排序来实现离散化。
时间复杂度分析:建树的过程就是归并排序,其时间复杂度为O(nlog(n))。查询时:二分查找第k小元素的复杂度为O(log(n)),访问一个节点的复杂度为O(log(n))。因此,查询一次的复杂度为O((logn)^3),总复杂度为O(m(logn)^3)。
空间复杂度:O(n)。
【代码】
1 #include <iostream> 2 #include <cstdlib> 3 #include <algorithm> 4 #include <vector> 5 #define MID(x, y) ((x + y) >> 1) 6 #define lson(x) (x << 1) 7 #define rson(x) ((x << 1) | 1) 8 9 using namespace std; 10 11 const int maxn = 100010; 12 const int maxm = 50005; 13 14 int a[maxn << 4]; 15 vector<int> tree[maxm << 4]; 16 17 void build(int root, int L, int R) 18 { 19 if (L == R) { 20 tree[root].push_back(a[L]); 21 return; 22 } 23 build(lson(root), L, MID(L, R)), build(rson(root), MID(L, R) + 1, R); 24 tree[root].resize(R - L + 1); 25 merge(tree[lson(root)].begin(), tree[lson(root)].end(), tree[rson(root)].begin(), 26 tree[rson(root)].end(), tree[root].begin()); 27 } 28 29 int query(int root, int l, int r, int L, int R, int x) 30 { 31 if (r < L || l > R)return 0; 32 if (L <= l && r <= R) { 33 return upper_bound(tree[root].begin(), tree[root].end(), x) - tree[root].begin(); 34 } 35 else { 36 int re1 = 0, re2 = 0; 37 re1 = query(lson(root), l, MID(l, r), L, R, x); 38 re2 = query(rson(root), MID(l, r) + 1, r, L, R, x); 39 return re1 + re2; 40 } 41 } 42 43 int main() 44 { 45 int array_size, quest_n, i = 0, j, k, l, r, mid, ans; 46 scanf("%d %d", &array_size, &quest_n); 47 for (i = 1; i <= array_size; i++) scanf("%d", &a[i]); 48 build(1, 1, array_size); 49 sort(a + 1, a + array_size + 1); 50 while (quest_n--) { 51 scanf("%d %d %d", &i, &j, &k); 52 l = 1, r = array_size; 53 mid = 0, ans = 0; 54 while (l <= r) { 55 mid = MID(l, r); 56 if (query(1, 1, array_size, i, j, a[mid]) >= k) { 57 ans = mid; 58 r = mid - 1; 59 } 60 else l = mid + 1; 61 } 62 printf("%d ", a[ans]); 63 } 64 return 0; 65 }