POJ

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.