首页 > 代码库 > POJ2104 区间第k小
POJ2104 区间第k小
题意就是区间第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 then12 begin13 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 begin22 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 begin29 mid:=(l+r)>>1;lm:=mid-l+1;lp:=l;rp:=mid+1;30 for i:=l to mid do31 if a[i]<a[mid] then dec(lm);32 for i:=l to r do33 begin34 if i=l then s[h,i]:=0 else s[h,i]:=s[h,i-1];35 if t[h,i]=a[mid] then36 begin37 if lm<>0 then38 begin39 dec(lm);inc(s[h,i]);t[h+1,lp]:=t[h,i];inc(lp);40 end41 else begin t[h+1,rp]:=t[h,i];inc(rp);end;42 end43 else44 if t[h,i]<a[mid] then begin inc(s[h,i]);t[h+1,lp]:=t[h,i];inc(lp);end45 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 begin54 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 begin62 build(0,1,n);63 for i:=1 to m do64 begin65 readln(x,y,k);66 writeln(find(0,1,n,x,y,k));67 end;68 end;69 begin70 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 repeat11 while b[a[i]]<b[x] do inc(i);12 while b[a[j]]>b[x] do dec(j);13 if i<=j then begin14 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 begin24 if l=r then exit;25 mid:=(l+r+1)>> 1;p:=0;26 for i:=l to r do27 if d[h,i]<mid then begin28 d[h+1,l+p]:=d[h,i];29 inc(p);s[h,i]:=p;30 end else begin31 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 begin40 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<k44 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 begin49 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 begin55 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 repeat11 while a[i]<m do inc(i);12 while a[j]>m do dec(j);13 if i<=j then14 begin15 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 begin25 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 begin33 mid:=(l+r)>>1;p:=0;34 for i:=l to r do35 if z[h,i]<=mid then36 begin37 z[h+1,l+p]:=z[h,i];38 inc(p);39 s[h,i]:=p;40 end41 else42 begin43 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 begin53 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 begin61 for i:=1 to n do z[1,rk[i]]:=i;62 build(1,1,n);63 for i:=1 to m do64 begin65 readln(x,y,k);66 writeln(b[rk[find(1,1,n,x,y,k)]]);67 end;68 end;69 begin70 init;71 main;72 end.
盾哥的代码风格确实比我好很多，值得学习
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。