至此，我的划分树模版终于完成
1 const maxn=100000+10; 2 var s,t:array[0..20,0..maxn] of longint; 3 a,b,rk:array[0..maxn] of longint; 4 i,j,n,m,x,y,k:longint; 5 procedure sort(l,r:longint); 6 var i,j,m,temp:longint; 7 begin 8 i:=l;j:=r;x:=a[(i+j)>>1]; 9 repeat 10 while b[a[i]]<b[x] do inc(i); 11 while b[a[j]]>b[x] do dec(j); 12 if i<=j then 13 begin 14 y:=a[i];a[i]:=a[j];a[j]:=y; 15 inc(i);dec(j); 16 end; 17 until i>j; 18 if i<r then sort(i,r); 19 if j>l then sort(l,j); 20 end; 21 procedure init; 22 begin 23 readln(n,m); 24 for i:=1 to n do read(b[i]); 25 for i:=1 to n do a[i]:=i; 26 sort(1,n); 27 end; 28 procedure build(h,l,r:longint); 29 var i,p,mid:longint; 30 begin 31 mid:=(l+r)>>1;p:=0; 32 for i:=l to r do 33 if t[h,i]<=mid then 34 begin 35 t[h+1,l+p]:=t[h,i]; 36 inc(p); 37 s[h,i]:=p; 38 end 39 else 40 begin 41 t[h+1,mid+1+i-p-l]:=t[h,i]; 42 s[h,i]:=p; 43 end; 44 if l=r then exit; 45 build(h+1,l,mid); 46 build(h+1,mid+1,r); 47 end; 48 function find(h,l,r,x,y,k:longint):longint; 49 var ll,rr,mid:longint; 50 begin 51 if l=r then exit(t[h,l]); 52 mid:=(l+r)>>1; 53 if l=x then ll:=0 else ll:=s[h,x-1];rr:=s[h,y]-ll; 54 if rr>=k then exit(find(h+1,l,mid,l+ll,l+rr+ll-1,k)) 55 else exit(find(h+1,mid+1,r,mid+1+x-l-ll,mid+1+y-l-rr-ll,k-rr)); 56 end; 57 procedure main; 58 begin 59 for i:=1 to n do t[0,a[i]]:=i; 60 build(0,1,n); 61 for i:=1 to m do 62 begin 63 readln(x,y,k); 64 writeln(b[a[find(0,1,n,x,y,k)]]); 65 end; 66 end; 67 begin 68 assign(input,'input.txt');assign(output,'output.txt'); 69 reset(input);rewrite(output); 70 init; 71 main; 72 close(input);close(output); 73 end.
其中有一个技巧是从盾哥那里学来的，就是求sa数组，不用更改原数组，而是b[a[i]]成为一个有序数组即可，对sort稍作修改就可以
这估计是c++党没有的福利吧（偷笑……）
ps：貌似这个版本可以支持的操作不多，不如HDU3473求中位数，不过貌似可以开一个结构体，记录下它的原值然后乱搞也行？
但还是把两个版本的都记一下吧
1 var s,t:array[0..20,0..200000] of longint; 2 a,rk:array[0..200000] of longint; 3 i,n,m,x,y,k,j:longint; 4 procedure sort(l,r:longint); 5 var i,j,m,temp:longint; 6 begin 7 i:=l;j:=r;m:=a[(i+j)>>1]; 8 repeat 9 while a[i]<m do inc(i); 10 while a[j]>m do dec(j); 11 if i<=j then 12 begin 13 temp:=a[i];a[i]:=a[j];a[j]:=temp; 14 inc(i);dec(j); 15 end; 16 until i>j; 17 if i<r then sort(i,r); 18 if j>l then sort(l,j); 19 end; 20 procedure init; 21 begin 22 readln(n,m); 23 for i:=1 to n do read(a[i]);t[0]:=a; 24 sort(1,n); 25 end; 26 procedure build(h,l,r:longint); 27 var mid,i,lp,rp,lm:longint; 28 begin 29 mid:=(l+r)>>1;lm:=mid-l+1;lp:=l;rp:=mid+1; 30 for i:=l to mid do 31 if a[i]<a[mid] then dec(lm); 32 for i:=l to r do 33 begin 34 if i=l then s[h,i]:=0 else s[h,i]:=s[h,i-1]; 35 if t[h,i]=a[mid] then 36 begin 37 if lm<>0 then 38 begin 39 dec(lm);inc(s[h,i]);t[h+1,lp]:=t[h,i];inc(lp); 40 end 41 else begin t[h+1,rp]:=t[h,i];inc(rp);end; 42 end 43 else 44 if t[h,i]<a[mid] then begin inc(s[h,i]);t[h+1,lp]:=t[h,i];inc(lp);end 45 else begin t[h+1,rp]:=t[h,i];inc(rp);end; 46 end; 47 if l=r then exit; 48 build(h+1,l,mid); 49 build(h+1,mid+1,r); 50 end; 51 function find(h,l,r,x,y,k:longint):longint; 52 var mid,ll,rr:longint; 53 begin 54 if l=r then exit(t[h,l]); 55 mid:=(l+r)>>1; 56 if l=x then ll:=0 else ll:=s[h,x-1];rr:=s[h,y]-ll; 57 if rr>=k then exit(find(h+1,l,mid,l+ll,l+ll+rr-1,k)) 58 else exit(find(h+1,mid+1,r,mid+1+x-l-ll,mid+1+y-l-ll-rr,k-rr)); 59 end; 60 procedure main; 61 begin 62 build(0,1,n); 63 for i:=1 to m do 64 begin 65 readln(x,y,k); 66 writeln(find(0,1,n,x,y,k)); 67 end; 68 end; 69 begin 70 init; 71 main; 72 end. 73