poj2104

裸的主席树，没什么好说的
  1 type node=record
  2        l,r,s:longint;
  3      end;
  4 var tree:array[0..2000010] of node;
  5     sa,rank,a,b,sum,head:array[0..100010] of longint;
  6     t,k,x,y,i,n,m,p:longint;
  7 
  8 procedure swap(var a,b:longint);
  9   var c:longint;
 10   begin
 11     c:=a;
 12     a:=b;
 13     b:=c;
 14   end;
 15 
 16 procedure sort(l,r: longint);
 17   var i,j,x:longint;
 18   begin
 19     i:=l;
 20     j:=r;
 21     x:=a[(l+r) shr 1];
 22     repeat
 23       while a[i]<x do inc(i);
 24       while x<a[j] do dec(j);
 25       if not(i>j) then
 26       begin
 27         swap(a[i],a[j]);
 28         swap(b[i],b[j]);
 29         inc(i);
 30         j:=j-1;
 31       end;
 32     until i>j;
 33     if l<j then sort(l,j);
 34     if i<r then sort(i,r);
 35   end;
 36 
 37 procedure update(x:longint);
 38   begin
 39     tree[x].s:=tree[tree[x].l].s+tree[tree[x].r].s;
 40   end;
 41 
 42 function build(l,r:longint):longint;
 43   var m,q:longint;
 44   begin
 45     inc(t);
 46     q:=t;
 47     if l=r then exit(t)
 48     else begin
 49       m:=(l+r) shr 1;
 50       tree[q].l:=build(l,m);
 51       tree[q].r:=build(m+1,r);
 52     end;
 53     exit(q);
 54   end;
 55 
 56 function pre(w,l,r:longint):longint;
 57   var m,q:longint;
 58   begin
 59     inc(t);
 60     q:=t;
 61     if l=r then
 62       tree[q].s:=sum[l]
 63     else begin
 64       m:=(l+r) shr 1;
 65       if rank[i]<=m then
 66       begin
 67         tree[q].l:=pre(tree[w].l,l,m);
 68         tree[q].r:=tree[w].r;
 69       end
 70       else begin
 71         tree[q].l:=tree[w].l;
 72         tree[q].r:=pre(tree[w].r,m+1,r);
 73       end;
 74       update(q);
 75     end;
 76     exit(q);
 77   end;
 78 
 79 function ask(x,y,l,r:longint):longint;
 80   var m,a,b:longint;
 81   begin
 82     if l=r then
 83       exit(sa[l])
 84     else begin
 85       m:=(l+r) shr 1;
 86       a:=tree[x].l;
 87       b:=tree[y].l;
 88   //    writeln(l,' ',m,' ',tree[b].s-tree[a].s);
 89       if tree[b].s-tree[a].s>=k then
 90         exit(ask(a,b,l,m))
 91       else begin
 92         k:=k-(tree[b].s-tree[a].s);
 93         exit(ask(tree[x].r,tree[y].r,m+1,r));
 94       end;
 95     end;
 96   end;
 97 
 98 begin
 99   readln(n,m);
100   for i:=1 to n do
101   begin
102     read(a[i]);
103     b[i]:=i;
104   end;
105   sort(1,n);
106   p:=1;
107   rank[b[1]]:=1;
108   sa[1]:=a[1];
109   for i:=2 to n do
110   begin
111     if a[i]<>a[i-1] then
112     begin
113       inc(p);
114       sa[p]:=a[i];
115     end;
116     rank[b[i]]:=p;
117   end;
118   t:=0;
119   head[0]:=build(1,p);
120   for i:=1 to n do
121   begin
122     inc(sum[rank[i]]);
123     head[i]:=pre(head[i-1],1,p);
124   end;
125   for i:=1 to m do
126   begin
127     readln(x,y,k);
128     writeln(ask(head[x-1],head[y],1,p));
129   end;
130 end.
View Code