http://acm.hdu.edu.cn/showproblem.php?pid=4251
n个数，求给定区间中间大小的元素的值
Sample Input
5
5 3 2 4 1
3
1 3
2 4
3 5
5
10 6 4 8 2
3
1 3
2 4
3 5
Sample Output
Case 1:
3
3
2
Case 2:
6
6
4
1
#include<cstdio>
2
#include<
string
>
3
#include<vector>
4
#include<algorithm>
5
#define
N 100009
6
using
namespace
std;
7
int
n;
8
int
arr[N];
//
原数据
9
int
od[N];
//
排序后
10
int
lfnum[
20
][N];
//
元素所在区间的当前位置进入左孩子的元素的个数
11
int
val[
20
][N];
//
记录第k层当前位置的元素的值
12
bool
cmp(
const
int
&x,
const
int
&y){
return
arr[x]<
arr[y];}
13
void
build(
int
l,
int
r,
int
d)
14
{
15
if
(l==r)
return
;
16
int
mid=(l+r)>>
1
,p=
0
;
17
for
(
int
i=l;i<=r;i++
)
18
{
19
if
(val[d][i]<=
mid)
20
{
21
val[d+
1
][l+p]=
val[d][i];
22
lfnum[d][i]=++
p;
23
}
24
else
25
{
26
lfnum[d][i]=
p;
27
val[d+
1
][mid+i+
1
-l-p]=
val[d][i];
28
}
29
}
30
build(l,mid,d+
1
);
31
build(mid+
1
,r,d+
1
);
32
}
33
//
求区间[s,e]第k大的元素
34
int
query(
int
s,
int
e,
int
k,
int
l=
1
,
int
r=n,
int
d=
0
)
35
{
36
if
(l==r)
return
l;
37
int
mid=(l+r)>>
1
,ss,ee;
38
ss=(s==l?
0
:lfnum[d][s-
1
]);
39
ee=
lfnum[d][e];
40
if
(ee-ss>=k)
return
query(l+ss,l+ee-
1
,k,l,mid,d+
1
);
41
return
query(mid+
1
+(s-l-ss),mid+
1
+(e-l-ee),k-(ee-ss),mid+
1
,r,d+
1
);
42
}
43
int
main()
44
{
45
int
cas=
0
,m,l,r;
46
while
(scanf(
"
%d
"
,&n)!=
EOF)
47
{
48
printf(
"
Case %d:\n
"
,++
cas);
49
for
(
int
i=
1
;i<=n;i++) scanf(
"
%d
"
,arr+i),od[i]=
i;
50
sort(od+
1
,od+n+
1
,cmp);
51
for
(
int
i=
1
;i<=n;i++) val[
0
][od[i]]=
i;
52
build(
1
,n,
0
);
53
scanf(
"
%d
"
,&
m);
54
while
(m--
)
55
{
56
int
num,k;
57
scanf(
"
%d%d
"
,&l,&
r);
58
k=(r-l)/
2
+
1
;
//
中间大小
59
num=
query(l,r,k);
60
int
ans=
arr[od[num]];
61
printf(
"
%d\n
"
,ans);
62
}
63
}
64
}
