Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

help。。。。。。。。。。。。用treap一直re,郁闷啊。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

Posted by ghk at 2009-01-06 14:04:06 on Problem 2761 and last updated at 2009-01-06 14:08:55
谁帮我改一下,或者给我数据,谢啦。。。。。。。。。。。。。。。。。
var n,m,i,j,ro,l:longint;
    t:array[0..100001] of record le,ri,si,key,pri,cnt:longint; end;
    x,y,k,nn,ans:array[0..50001] of longint;
procedure swap(var xx,yy:longint);
var tt:longint; begin tt:=xx; xx:=yy; yy:=tt; end;
procedure q(const le,ri:longint);
var ii,jj,xx:longint;
begin
 ii:=le; jj:=ri;
 xx:=x[nn[(ii+jj) shr 1]];
 repeat
  while x[nn[ii]]<xx do inc(ii);
  while xx<x[nn[jj]] do dec(jj);
  if ii<=jj
   then begin
         swap(nn[ii],nn[jj]);
         inc(ii);
         dec(jj);
        end;
 until ii>jj;
 if le<jj then q(le,jj);
 if ii<ri then q(ii,ri);
end;
procedure updata(const xx:longint);
begin t[xx].si:=t[t[xx].le].si+t[t[xx].ri].si+t[xx].cnt; end;
procedure lt(var xx:longint);
var yy:longint;
begin
 yy:=t[xx].ri;
 t[xx].ri:=t[yy].le;
 t[yy].le:=xx;
 updata(xx); updata(yy);
 xx:=yy;
end;
procedure rt(var xx:longint);
var yy:longint;
begin
 yy:=t[xx].le;
 t[xx].le:=t[yy].ri;
 t[yy].ri:=xx;
 updata(xx); updata(yy);
 xx:=yy;
end;
procedure insert(var xx:longint);
begin
 if xx=0
  then xx:=i
  else begin
        if t[i].key>t[xx].key
         then begin
               insert(t[xx].ri);
               if t[xx].pri<t[t[xx].ri].pri then lt(xx);
              end
         else if t[i].key<t[xx].key
               then begin
                     insert(t[xx].le);
                     if t[xx].pri<t[t[xx].le].pri then rt(xx);
                    end
               else inc(t[xx].cnt);
        updata(xx);
       end;
end;
procedure delete(var xx:longint);
begin
 if t[i].key<t[xx].key
  then delete(t[xx].le)
  else if t[i].key>t[xx].key
        then delete(t[xx].ri)
        else if t[xx].cnt>1
              then dec(t[xx].cnt)
              else if t[xx].le+t[xx].ri=0
                    then xx:=0
                    else begin
                          if t[t[xx].le].pri>t[t[xx].ri].pri
                           then rt(xx) else lt(xx);
                          delete(xx);
                         end;
 updata(xx);
end;
function find(const xx,kk:longint):longint;
begin
 if kk<=t[t[xx].le].si then exit(find(t[xx].le,kk));
 if kk<=t[t[xx].le].si+t[xx].cnt then exit(t[xx].key);
 exit(find(t[xx].ri,kk-t[t[xx].le].si-t[xx].cnt));
end;
begin
 randomize;
 read(n,m);
 for i:=1 to n do
  with t[i] do
   begin
    read(key);
    pri:=random(maxlongint);
    cnt:=1;
   end;
 for i:=1 to m do
  begin
   read(x[i],y[i],k[i]);
   if x[i]>y[i] then swap(x[i],y[i]);
   nn[i]:=i;
  end;
 q(1,m);
 t[0].pri:=-1;
 y[0]:=x[nn[1]]-1;
 x[0]:=maxlongint;
 for j:=1 to m do
  begin
   for i:=x[nn[j-1]] to x[nn[j]]-1 do delete(ro);
   for i:=y[nn[j-1]]+1 to y[nn[j]] do insert(ro);
   ans[nn[j]]:=find(ro,k[nn[j]]);
  end;
 for i:=1 to m do writeln(ans[i]);
end.

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator