1773【RMQ&LCA】Cartesian Tree(笛卡尔树)(2)

end;

procedure dfs(l,r:longint); var x,y,z:longint; begin

if l=r then exit; x:=rmq(l,r); y:=0; z:=0;

if x<>l then begin y:=rmq(l,x-1);

if (k[y]a[x]) then begin d[b[x],2]:=b[y]; d[b[y],1]:=b[x]; dfs(l,x-1); end; end;

if x<>r then begin z:=rmq(x+1,r);

if (k[z]>k[x]) and (a[z]>a[x]) then begin d[b[x],3]:=b[z]; d[b[z],1]:=b[x]; dfs(x+1,r); end; end; end;

begin

readln(n);

for i:=1 to n do begin

readln(k[i],a[i]); b[i]:=i; end; kp(1,n); rmq1(n); dfs(1,n);

writeln('YES');

for i:=1 to n do writeln(d[i,1],' ',d[i,2],' ',d[i,3]); end.