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