归并树，总WA
请问哪位有pascal的标程？C的看着太别扭，有的还不明白……
program pku_2104;
type
  treetype=record
    lf,rf,left,right:longint;
  end;
  treetype2=record
    left,right,zhi,size:longint;
  end;
var
  tree:array[0..200005]of treetype;{外边的树}
  treen:array[0..3400000]of treetype2;{建在外树顶点上的树}
  root:array[1..100000]of longint;{内部树的根顶点编号}
  a,b:array[0..100000]of longint;
  bianh,yings,yong:array[0..100000]of longint;{bianh第i名是第几个数，yings第i个数是第几名}
  i,j,k,n,m,p,q,r,s,len,lenn,sj,xj:longint;
procedure swap(var a,b:longint);
var
t:longint;
begin
t:=a;
a:=b;
b:=t;
end;
procedure kuaipai(l,r:longint);
  var i,j,min,x:longint;
  begin
    i:=l;j:=r;min:=a[(l+r) div 2];
    repeat
      while a[i]<min do inc(i);
      while a[j]>min do dec(j);
      if i<=j then begin
                    swap(a[i],a[j]);
                    swap(bianh[i],bianh[j]);
                    inc(i);dec(j);
                  end;
    until i>j;
    if i<r then kuaipai(i,r);
    if j>l then kuaipai(l,j);
end;
procedure kuaipai2(l,r:longint);
  var i,j,min,x:longint;
  begin
    i:=l;j:=r;min:=yong[(l+r) div 2];
    repeat
      while yong[i]<min do inc(i);
      while yong[j]>min do dec(j);
      if i<=j then begin
                    swap(yong[i],yong[j]);
                    inc(i);dec(j);
                  end;
    until i>j;
    if i<r then kuaipai2(i,r);
    if j>l then kuaipai2(l,j);
end;
procedure build2(b,e:longint);
var
  t,k:longint;
begin
  t:=(b+e)div 2;
  inc(lenn);
  treen[lenn].size:=e-b+1;
  treen[lenn].zhi:=yong[t];
  k:=lenn;
  if b<e then begin
    treen[k].left:=lenn+1;
    build2(b,t);
    treen[k].right:=lenn+1;
    build2(t+1,e);
  end;
end;
procedure build1(b,e:longint);
var
  t,k:longint;
begin
  t:=(b+e) div 2;
  inc(len);
  tree[len].lf:=b;
  tree[len].rf:=e;
  root[len]:=lenn+1;
  for i:=b to e do yong[i]:=yings[i];
  kuaipai2(b,e);
  build2(b,e);
  k:=len;
  if b<e then begin
    tree[k].left:=len+1;
    build1(b,t);
    tree[k].right:=len+1;
    build1(t+1,e);
  end;
end;
function find2(j,p:longint):longint;
var
than,tmp,t:longint;
begin
tmp:=p;
than:=0;
while treen[tmp].size<>1 do
begin
if j>treen[tmp].zhi then begin
than:=than+treen[treen[tmp].left].size;
tmp:=treen[tmp].right;
end
else tmp:=treen[tmp].left;
end;
if j>treen[tmp].zhi then inc(than);
find2:=than;
end;
function find(b,e,j,p:longint):longint;
var
t,s:longint;
begin
  if (tree[p].lf>=b)and(tree[p].rf<=e) then begin
    find:=find2(j,root[p]);
    exit;
  end;
  s:=0;
  t:=(tree[p].lf+tree[p].rf)div 2;
  if b<=t then s:=s+find(b,e,j,tree[p].left);
  if e>t then s:=s+find(b,e,j,tree[p].right);
  find:=s;
end;
begin
  assign(input,'pku_2104.in');
  assign(output,'pku_2104.out');
  reset(input);
  rewrite(output);
  readln(n,m);
  len:=0;
  lenn:=0;
  fillchar(treen,sizeof(treen),0);
  fillchar(tree,sizeof(tree),0);
  fillchar(root,sizeof(root),0);
fillchar(bianh,sizeof(bianh),0);
  fillchar(yong,sizeof(yong),0);
  fillchar(yings,sizeof(yings),0);
  
  for i:=1 to n do read(a[i]);
  b:=a;
  for i:=1 to n do bianh[i]:=i;
  kuaipai(1,n);
  for i:=1 to n do yings[bianh[i]]:=i;
  build1(1,n);
  for i:=1 to m do begin
  readln(p,q,r);
  xj:=1;
  sj:=n;
  r:=r-1;
  while xj<sj-1 do
  begin
    j:=(sj+xj)div 2;
    s:=find(p,q,j,1);
    {if s=r then break
    else }if s>r then sj:=j-1 else xj:=j;
  end;
  s:=find(p,q,xj+1,1);
  if (s=r)and(xj=sj-1) then writeln(b[bianh[xj+1]]) else writeln(b[bianh[xj]]);
  end;
  close(input);
  close(output);
end.

• Re:求救！总是RE (3929) xycking 2010-02-18 21:51:47
  • Re:求救！总是RE (21) xycking 2010-02-18 22:00:56