又是不带修改的区间第k大，这次用的是一个不同的方法，划分树，划分树感觉上是模拟了快速排序的过程，依照pivot不断地往下划分，然后每一层多存一个toleft[i]数组，就可以知道在这一层里从0到i里有多少个被划分到了左子树，知道区间有多少个被分到左子树，就可以一路递归下去，不需要像函数式线段数一样，二分再加query，所以每次询问的复杂度也只是O(nlogn)，空间复杂度的话就是O(nlogn)，具体的介绍很多个链接都有，具体看下面给出的两个链接，它们对我起到非常大的帮助。
http://blog.csdn.net/famousdt/article/details/7064866
http://www.cnblogs.com/pony1993/archive/2012/07/17/2594544.html
写的时候尤其是递归询问区间的时候很容易出现off-by-one error，我在纸上比划了很久才搞清楚的。有点微弱呀－ －0下面是代码。800多ms，是函数式线段数的时间的一半吧
|
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 |
#pragma warning(disable:4996)#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<algorithm>#include<vector>#include<cmath>#define maxn 100000using
namespace std;int
tree[22][maxn + 50];int
toleft[22][maxn + 50];int
as[maxn + 50];int
n, q;void
build(int
l, int
r, int
dep){ if
(l == r) return; int
mid = (l + r) >> 1; int
same = mid - l + 1; for
(int i = l; i <= r; i++){ if
(tree[dep][i] < as[mid]){ same--; } } int
ls = l; int
rs = mid + 1; for
(int i = l; i <= r; i++){ if
(tree[dep][i] < as[mid]) tree[dep + 1][ls++] = tree[dep][i]; else
if (tree[dep][i] == as[mid] && same) tree[dep + 1][ls++] = tree[dep][i], same--; else
tree[dep + 1][rs++] = tree[dep][i]; toleft[dep][i] = toleft[dep][l - 1] + ls - l; } build(l, mid, dep + 1); build(mid + 1, r, dep + 1);}int
query(int
left, int
right, int
k, int
L, int
R, int
dep){ if
(left == right) return
tree[dep][left]; int
mid = (L + R) >> 1; int
x = toleft[dep][left - 1] - toleft[dep][L - 1]; int
y = toleft[dep][right] - toleft[dep][L - 1]; int
rx = left - 1 - L + 1 - x; int
ry = right - L + 1 - y; int
cnt = y - x; if
(cnt >= k) return
query(L + x, L + y - 1, k, L, mid, dep + 1); // 注意off-by-one error. else
return query(mid + 1 + rx,mid + 1 + ry - 1, k - cnt, mid + 1, R, dep + 1);}int
main(){ while
(cin >> n >> q) { for
(int i = 1; i <= n; i++){ scanf("%d", as + i); tree[0][i] = as[i]; } sort(as + 1, as + n + 1); build(1, n, 0); int
li, ri, ki; for
(int i = 0; i < q; i++){ scanf("%d%d%d", &li, &ri, &ki); printf("%d\n", query(li, ri, ki, 1, n, 0)); } } return
0;} |
原文：http://www.cnblogs.com/chanme/p/3562172.html