http://acm.hdu.edu.cn/showproblem.php?pid=4251
n個數(shù)，求給定區(qū)間中間大小的元素的值
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];
//
原數(shù)據(jù)
9
int
od[N];
//
排序后
10
int
lfnum[
20
][N];
//
元素所在區(qū)間的當前位置進入左孩子的元素的個數(shù)
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
//
求區(qū)間[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
}
?
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
