引
如题:POJ2014
给定一$n$个元素的数组,每次查询$[l,r]$区间内从小到大第k个数.
朴素解法为将数组$[l,r]$内的数排序,然后选择第$k$个即可.最坏情况$O(m*n)$.
这个时候,就需要更好的数据结构,划分树/归并树.
定义
原数组为${4,2,5,7,1,8,3,6}$,在每次划分左右子树时的中值,都用红色表明.小于中值的进入左子树,大于中值的进入右子树.
观察我们发现,每一层都是数组$n$,只不过顺序有了变化.而对于$log2(1e9)$这个数,也不过$20$.所以我们定义一个$tree[20][n]$的数组,用来存树.
1 | //toleft稍后再讲 |
建树
我们定义一个数组$toleft[20][MAXN]$,其指在某数的左边所有进入左子树的数的个数.
toleft数组
1 | 第一次划分 |
1 | void built(int l, int r, int dep) |
查询
类似于线段树的单点查询
只需要考虑一个不等式
$toleft[dep][r] - toleft[dep][l - 1]\leq k$
如果成立,说明这个数被划进了左子树.那么大区间$[L,(L+R)>>1]$,小区间$[l,r]$变为
$$[L + toleft[dep][l - 1] - toleft[dep][L - 1],newl + cnt - 1]$$
如果
$$toleft[dep][r] - toleft[dep][l - 1]<k$$
那么,这个数就被划进了右子树,那么大区间变为$[(L+R)>>1+1,R]$,小区间变为
$$[newr - (r - l - cnt),r + toleft[dep][R] - toleft[dep][r]]$$.
这样不断递归,当小区间$l==r$时,便确定了从小到大第$k$个数是几.
1 | int query(int L, int R, int l, int r, int dep, int k) |
完整代码
当想查询从大到小第$k$个数,则将1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
```cpp
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<string.h>
#include<map>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 1e5 + 10;
int tree[20][MAXN], sorted[MAXN], toleft[20][MAXN];
void built(int l, int r, int dep)
{
if (l == r)
return;
int mid = (l + r) >> 1, same = mid - l + 1;
for (int i = l; i <= r; i++)
if (tree[dep][i] < sorted[mid])
same--;
int lpos = l, rpos = mid + 1;
for (int i = l; i <= r; i++) {
if (tree[dep][i] < sorted[mid])
tree[dep + 1][lpos++] = tree[dep][i];
else if (tree[dep][i] == sorted[mid] && same > 0) {
tree[dep + 1][lpos++] = tree[dep][i];
same--;
}
else
tree[dep + 1][rpos++] = tree[dep][i];
toleft[dep][i] = toleft[dep][l - 1] + lpos - l;
}
built(l, mid, dep + 1);
built(mid + 1, r, dep + 1);
}
int query(int L, int R, int l, int r, int dep, int k)
{
if (l == r)
return tree[dep][l];
int mid = (L + R) >> 1;
int cnt = toleft[dep][r] - toleft[dep][l - 1];
if (cnt >= k) {
int newl = L + toleft[dep][l - 1] - toleft[dep][L - 1];
int newr = newl + cnt - 1;
return query(L, mid, newl, newr, dep + 1, k);
}
else {
int newr = r + toleft[dep][R] - toleft[dep][r];
int newl = newr - (r - l - cnt);
return query(mid + 1, R, newl, newr, dep + 1, k - cnt);
}
}
int main()
{
int n, m;
while (cin >> n >> m) {
memset(tree, 0, sizeof(tree));
for (int i = 1; i <= n; i++) {
cin >> tree[0][i];
sorted[i] = tree[0][i];
}
sort(sorted + 1, sorted + n + 1);
built(1, n, 0);
int s, t, k;
while (m--) {
cin >> s >> t >> k;
cout << query(1, n, s, t, 0, k) << endl;
}
}
return 0;
}