POJ 2104

传送门

整体二分
主席树

整体二分

首先把序列排成有序的

然后二分答案,把$\leq mid$的数扔到树状数组里,看每个询问的区间里的数够不够$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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
program poj_2104;
type rec=record k,p:longint; end;
ask_op=record l,r,k,id,cur:longint; end;
var bit:array[1..100000]of longint;
q,q1,q2:array[1..5000]of ask_op;
ans:array[1..5000]of longint;
a:array[1..100000]of rec;
n,m,i:longint;
function c(x:longint):longint;
begin
exit(x and -x);
end;
procedure plus(p,d:longint);
begin
while p<=n do
begin
inc(bit[p],d);
inc(p,c(p));
end;
end;
function query(p:longint):longint;
begin
query:=0;
while p>0 do
begin
inc(query,bit[p]);
dec(p,c(p));
end;
end;
procedure qsort(l,r:longint);
var i,j:longint;
mid,p:rec;
begin
i:=l;
j:=r;
mid:=a[(l+r)>>1];
repeat
while a[i].k<mid.k do inc(i);
while a[j].k>mid.k do dec(j);
if i<=j then
begin
p:=a[i];
a[i]:=a[j];
a[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
procedure solve(hd,tl,l,r:longint);
var i,mid,l1,l2,t:longint;
begin
if hd>tl then exit;
if l=r then
begin
for i:=hd to tl do ans[q[i].id]:=l;
exit;
end;
mid:=(l+r)>>1;
l1:=0;
l2:=0;
for i:=l to mid do plus(a[i].p,1);
for i:=hd to tl do
begin
t:=query(q[i].r)-query(q[i].l-1);
if q[i].cur+t>=q[i].k then
begin
inc(l1);
q1[l1]:=q[i];
end else
begin
inc(q[i].cur,t);
inc(l2);
q2[l2]:=q[i];
end;
end;
for i:=l to mid do plus(a[i].p,-1);
for i:=1 to l1 do q[hd+i-1]:=q1[i];
for i:=1 to l2 do q[hd+l1+i-1]:=q2[i];
solve(hd,hd+l1-1,l,mid);
solve(hd+l1,tl,mid+1,r);
end;
begin
readln(n,m);
for i:=1 to n do
begin
read(a[i].k);
a[i].p:=i;
end;
qsort(1,n);
for i:=1 to m do with q[i] do
begin
readln(l,r,k);
id:=i;
cur:=0;
end;
solve(1,m,1,n);
for i:=1 to m do writeln(a[ans[i]].k);
end.

主席树

这个是裸的…就不用讲了吧…


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
76
77
78
79
80
81
82
83
84
85
86
87
program poj_2104;
type rec=record k,p:longint; end;
var s:array[0..2000000]of record lc,rc,l,r,cnt:longint; end;
n,m,i,l,r,tot,t:longint;
a:array[1..100000]of rec;
k,rt:array[0..100000]of longint;
procedure build(var t:longint;l,r:longint);
var mid:longint;
begin
inc(tot);
t:=tot;
s[t].l:=l;
s[t].r:=r;
s[t].cnt:=0;
if l=r then exit;
mid:=(l+r)>>1;
build(s[t].lc,l,mid);
build(s[t].rc,mid+1,r);
end;
procedure qsort(l,r:longint);
var i,j:longint;
mid,p:rec;
begin
i:=l;
j:=r;
mid:=a[(l+r)>>1];
repeat
while a[i].k<mid.k do inc(i);
while a[j].k>mid.k do dec(j);
if i<=j then
begin
p:=a[i];
a[i]:=a[j];
a[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
procedure modify(var t:longint;p:longint);
var mid:longint;
begin
inc(tot);
s[tot]:=s[t];
t:=tot;
inc(s[t].cnt);
if s[t].l=s[t].r then exit;
mid:=(s[t].l+s[t].r)>>1;
if p<=mid then modify(s[t].lc,p) else modify(s[t].rc,p);
end;
function query(l,r,t:longint):longint;
var k:longint;
begin
if s[l].l=s[l].r then exit(s[l].l);
k:=s[s[r].lc].cnt-s[s[l].lc].cnt;
if t<=k then exit(query(s[l].lc,s[r].lc,t)) else exit(query(s[l].rc,s[r].rc,t-k));
end;
begin
readln(n,m);
for i:=1 to n do
begin
read(a[i].k);
a[i].p:=i;
end;
qsort(1,n);
for i:=1 to n do k[a[i].p]:=i;
tot:=0;
fillchar(s,sizeof(s),0);
build(rt[0],1,n);
for i:=1 to n do
begin
rt[i]:=rt[i-1];
modify(rt[i],k[i]);
end;
for i:=1 to m do
begin
readln(l,r,t);
writeln(a[query(rt[l-1],rt[r],t)].k);
end;
end.