poj2104 K-th Number（主席树静态区间第k大）

 1 program rrr(input,output);
 2 type
 3   treetype=record
 4      lc,rc,s:longint;
 5   end;
 6 var
 7   a:array[0..100010*30]of treetype;
 8   rot,idx,b,c:array[0..100010]of longint;
 9   n,m,i,cnt,l,r,j,k,mid,x,y,t:longint;
10 procedure sort(q,h:longint);
11 var
12   i,j,x,t:longint;
13 begin
14    i:=q;j:=h;x:=b[(i+j)>>1];
15    repeat
16      while b[i]<x do inc(i);
17      while x<b[j] do dec(j);
18      if i<=j then
19         begin
20            t:=b[i];b[i]:=b[j];b[j]:=t;
21            t:=idx[i];idx[i]:=idx[j];idx[j]:=t;
22            inc(i);dec(j);
23         end;
24    until i>j;
25    if j>q then sort(q,j);
26    if i<h then sort(i,h);
27 end;
28 procedure build(k,l,r:longint);
29 var
30   mid:longint;
31 begin
32    a[k].s:=0;
33    if l=r then exit;
34    mid:=(l+r)>>1;
35    inc(cnt);a[k].lc:=cnt;build(cnt,l,mid);
36    inc(cnt);a[k].rc:=cnt;build(cnt,mid+1,r);
37 end;
38 procedure add(x:longint);
39 begin
40    inc(cnt);rot[i]:=cnt;
41    j:=cnt;k:=rot[i-1];a[j].s:=a[k].s+1;
42    l:=1;r:=n;
43    while l<r do
44       begin
45          mid:=(l+r)>>1;inc(cnt);
46          if x>mid then
47             begin
48                l:=mid+1;
49                a[j].lc:=a[k].lc;k:=a[k].rc;
50                a[j].rc:=cnt;j:=cnt;a[j].s:=a[k].s+1;
51             end
52          else
53             begin
54                r:=mid;
55                a[j].rc:=a[k].rc;k:=a[k].lc;
56                a[j].lc:=cnt;j:=cnt;a[j].s:=a[k].s+1;
57             end;
58       end;
59 end;
60 function ask(x,y,t:longint):longint;
61 begin
62    j:=rot[x-1];k:=rot[y];l:=1;r:=n;cnt:=0;
63    while l<r do
64       begin
65          mid:=(l+r)>>1;
66          if cnt+a[a[k].lc].s-a[a[j].lc].s>=t then begin r:=mid;j:=a[j].lc;k:=a[k].lc; end
67          else begin cnt:=cnt+a[a[k].lc].s-a[a[j].lc].s;l:=mid+1;j:=a[j].rc;k:=a[k].rc; end;
68       end;
69    exit(b[l]);
70 end;
71 begin
72    assign(input,‘r.in‘);assign(output,‘r.out‘);reset(input);rewrite(output);
73    readln(n,m);
74    for i:=1 to n do begin read(b[i]);idx[i]:=i; end;
75    sort(1,n);
76    for i:=1 to n do c[idx[i]]:=i;
77    cnt:=1;rot[0]:=1;
78    build(1,1,n);
79    for i:=1 to n do add(c[i]);
80    //for i:=1 to 40 do writeln(a[rot[i]].s);
81    for i:=1 to m do begin readln(x,y,t);writeln(ask(x,y,t)); end;
82    close(input);close(output);
83 end.