题意就是区间第k大……
题解：
前段时间用主席树搞掉了……
如今看到划分树，是在想来写一遍，结果18号对着学长的代码调了一上午连样例都没过，好桑心……
今天在做NOI2010超级钢琴，忽然发现用划分树很直观，果断决定再战划分树
对着网上的c++代码抄了一遍，A了，可是这编程复杂度有点高，忽然又看见盾哥的代码
很简短，和我原先的代码差不多，他怎么能A了呢……（后来发现区间第k小，我却写的第k大……sb啊）
考虑到盾哥的程序用到了离散化，因此没有考虑存在两个数相等的情况，这样就使代码减少很多
我报着试一试的心态把我认为肯定对的代码随机生成了几组大数据和盾哥的程序对拍，然后就对上了
好的，以后就用盾哥的程序
代码：
c++翻译来的：
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.
盾哥的：
1 program poj2104; const maxn=200000; 2 var 3 a,b:array[0..maxn] of longint; 4 s,d:array[1..20,0..maxn] of longint; 5 n,m,i,j,x,y,z,ls,rs,mid,p:longint; 6 7 procedure sort(l,r:longint); var i,j,x,y:longint; 8 begin 9 i:=l;j:=r;x:=a[(i+j)>> 1]; 10 repeat 11 while b[a[i]]<b[x] do inc(i); 12 while b[a[j]]>b[x] do dec(j); 13 if i<=j then 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 l<j then sort(l,j); 19 if i<r then sort(i,r); 20 end; 21 22 procedure buildtree(h,l,r:longint);var mid:longint; 23 begin 24 if l=r then exit; 25 mid:=(l+r+1)>> 1;p:=0; 26 for i:=l to r do 27 if d[h,i]<mid then begin 28 d[h+1,l+p]:=d[h,i]; 29 inc(p);s[h,i]:=p; 30 end else begin 31 d[h+1,mid+i-l-p]:=d[h,i]; 32 s[h,i]:=p; 33 end; 34 buildtree(h+1,l,mid-1); 35 buildtree(h+1,mid,r); 36 end; 37 38 function find(h,ll,rr,l,r,k:longint):longint; 39 begin 40 if l=r then exit(d[h,r]); 41 if l=ll then ls:=0 else ls:=s[h,l-1]; 42 rs:=s[h,r];mid:=(ll+rr+1)>> 1; 43 if rs-ls<k 44 then find:=find(h+1,mid,rr,l-ll-ls+mid,r-ll-rs+mid,k-rs+ls) 45 else find:=find(h+1,ll,mid-1,ls+ll,rs+ll-1,k); 46 end; 47 48 begin 49 readln(n,m); 50 for i:=1 to n do begin read(b[i]);a[i]:=i; end; 51 sort(1,n); 52 for i:=1 to n do d[1,a[i]]:=i; 53 buildtree(1,1,n); 54 for i:=1 to m do begin 55 readln(x,y,z); 56 writeln(b[a[find(1,1,n,x,y,z)]]); 57 end; 58 end.
我最先抄的：
1 const maxn=100000+10; 2 type arrtype=array[0..maxn] of longint; 3 var s,z:array[0..20,0..maxn] of longint; 4 a,b,rk:arrtype; 5 i,j,n,m,x,y,k:longint; 6 procedure sort(var a:arrtype;l,r:longint); 7 var i,j,m,temp:longint; 8 begin 9 i:=l;j:=r;m:=a[(i+j)>>1]; 10 repeat 11 while a[i]<m do inc(i); 12 while a[j]>m do dec(j); 13 if i<=j then 14 begin 15 temp:=a[i];a[i]:=a[j];a[j]:=temp; 16 temp:=rk[i];rk[i]:=rk[j];rk[j]:=temp; 17 inc(i);dec(j); 18 end; 19 until i>j; 20 if i<r then sort(a,i,r); 21 if j>l then sort(a,l,j); 22 end; 23 procedure init; 24 begin 25 readln(n,m); 26 for i:=1 to n do read(a[i]);readln;b:=a; 27 for i:=1 to n do rk[i]:=i; 28 sort(a,1,n); 29 end; 30 procedure build(h,l,r:longint); 31 var i,p,mid:longint; 32 begin 33 mid:=(l+r)>>1;p:=0; 34 for i:=l to r do 35 if z[h,i]<=mid then 36 begin 37 z[h+1,l+p]:=z[h,i]; 38 inc(p); 39 s[h,i]:=p; 40 end 41 else 42 begin 43 z[h+1,mid+1+i-p-l]:=z[h,i]; 44 s[h,i]:=p; 45 end; 46 if l=r then exit; 47 build(h+1,l,mid); 48 build(h+1,mid+1,r); 49 end; 50 function find(h,l,r,x,y,k:longint):longint; 51 var ll,rr,mid:longint; 52 begin 53 if l=r then exit(z[h,l]); 54 mid:=(l+r)>>1; 55 if l=x then ll:=0 else ll:=s[h,x-1];rr:=s[h,y]; 56 if rr-ll>=k then exit(find(h+1,l,mid,l+ll,l+rr-1,k)) 57 else exit(find(h+1,mid+1,r,mid+1+x-l-ll,mid+1+y-l-rr,k-(rr-ll))); 58 end; 59 procedure main; 60 begin 61 for i:=1 to n do z[1,rk[i]]:=i; 62 build(1,1,n); 63 for i:=1 to m do 64 begin 65 readln(x,y,k); 66 writeln(b[rk[find(1,1,n,x,y,k)]]); 67 end; 68 end; 69 begin 70 init; 71 main; 72 end.
盾哥的代码风格确实比我好很多，值得学习
UPD:
c++
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<algorithm> 5 #include<iostream> 6 #define inf 1000000000 7 #define maxn 100000+100 8 #define maxm 100000 9 using namespace std; 10 int n,m,a[maxn],sa[maxn],t[20][maxn],s[20][maxn]; 11 inline int read() 12 { 13 int x=0,f=1;char ch=getchar(); 14 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 15 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 16 return x*f; 17 } 18 void build(int h,int l,int r) 19 { 20 int mid=(l+r)>>1,num=0; 21 for(int i=l;i<=r;i++) 22 if (t[h][i]<=mid) 23 { 24 t[h+1][l+num]=t[h][i]; 25 s[h][i]=++num; 26 } 27 else 28 { 29 t[h+1][mid+1+i-l-num]=t[h][i]; 30 s[h][i]=num; 31 } 32 if(l==r)return; 33 build(h+1,l,mid); 34 build(h+1,mid+1,r); 35 } 36 int find(int h,int l,int r,int x,int y,int k) 37 { 38 if(l==r)return t[h][l]; 39 int mid=(l+r)>>1,ll,rr; 40 ll=(l==x)?0:s[h][x-1];rr=s[h][y]; 41 if(rr-ll>=k) return find(h+1,l,mid,l+ll,l+rr-1,k); 42 else return find(h+1,mid+1,r,mid+1+x-l-ll,mid+1+y-l-rr,k-(rr-ll)); 43 } 44 bool cmp(int x,int y) 45 { 46 return a[x]<a[y]; 47 } 48 int main() 49 { 50 freopen("input.txt","r",stdin); 51 freopen("output.txt","w",stdout); 52 n=read();m=read(); 53 for(int i=1;i<=n;i++){a[i]=read();sa[i]=i;} 54 sort(sa+1,sa+n+1,cmp); 55 for(int i=1;i<=n;i++)t[0][sa[i]]=i; 56 build(0,1,n); 57 for(int i=1;i<=m;i++) 58 { 59 int x,y,k; 60 x=read();y=read();k=read(); 61 printf("%d ",a[sa[find(0,1,n,x,y,k)]]); 62 } 63 return 0; 64 }