| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
help。。。。。。。。。。。。用treap一直re,郁闷啊。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。谁帮我改一下,或者给我数据,谢啦。。。。。。。。。。。。。。。。。
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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator