【RMQ&LCA】Cartesian Tree（笛卡尔树）
Time Limit:1000MS Memory Limit:65536K
Total Submit:6 Accepted:6
Description
笛卡尔树（tree.pas/c/cpp）
【问题描述】
让我们考虑一种特殊的二叉查找树，叫做笛卡尔树。回想一下，二叉查找树是有根有序的二叉树，这样，对于它的每一个节点x满足以下条件：在它的左子树的每个节点的数值小于x的数值，它的右子树的每个节点的数值大于x的数值。也就是说，如果我们用L(x)表示结点x的左子树，用R(x)表示结点x右子树，用kx表示该结点x的数值，那么对每个结点x我们有 如果y ∈ L(x)，那么ky < kx 如果z ∈ R(x)，那么kz > kx
若一棵二叉查找树被称为笛卡尔树，那么它的每一个结点x除了主要数值kx外还有一个附加数值ax，且这个数值符合堆的条件，即 如果y是x的父亲，那么ay < ax
因此，一棵笛卡尔树是一棵有根有序的二叉树，这样，它的每个节点拥有两个数值(k , a)和满足上述的三个条件。
给出一系列点，构建出它们的笛卡尔树，或检测构建出它们的笛卡尔树是不可能的。
Input
第一行包括一个整数N(1 <= N <= 50 000)，表示你要构建的笛卡尔树的点的对数。
接下来N行包括两个数字，k，a，|k|, |a| <= 30 000，保证每行的k和a是不同的。
Output
如果能构建出笛卡尔树则在第一行输出YES否则输出NO。
如果是YES，则在接下来N行输出这棵树。第i+1行输出第i个结点的父亲，左儿子，右儿子。如果这个结点无父亲或者儿子，则用0代替。 输入保证能构建出笛卡尔树的只有一种情况。
Sample Input
7 5 4 2 2 3 9 0 5 1 3 6 6 4 11
Sample Output
YES 2 3 6 0 5 1 1 0 7 5 0 0 2 4 0 1 0 0 3 0 0
Hint
本题数据不完整，请在本系统测试通过后到http://poj.org/problem?id=2201 提交完整测试！
Source
Northeastern Europe 2002, Northern Subregion
一开始看错题目，以为输入的第二个数字为K，纠结了很久也没有构造出一棵笛卡尔树。
先把数据按k从小到大排序，所得为树的中序遍历。
找出这棵树中a值最小的为该树的根，在排序中 根左面a值最小的为该树的左子树，在排序中 根右面a值最小的为该树的右子树。找最小值时，要用ST算法。 原作者：
var n:longint;
a:array[0..50000+1,1..3]of longint; f:array[0..16]of longint;
mi:array[0..50000+1,0..16,1..2]of longint; o:array[0..50000+1,1..3]of longint;
procedure init; var i:longint; begin f[0]:=1;
for i:=1 to 16 do f[i]:=f[i-1]*2; read(n);
for i:=1 to n do begin read(a[i,1],a[i,2]); a[i,3]:=i; end; end;
procedure qsort(l,r:longint); var i,j,k:longint; begin
if l>=r then exit;
i:=l; j:=r; k:=a[(l+r) div 2,1]; while i while a[i,1] a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0]; inc(i); dec(j); end; end; qsort(l,j); qsort(i,r); end; procedure dfs(l,r:longint); var i,t,ft,lt,rt,x:longint; begin if r<=l then exit; t:=trunc(ln(r-l+1)/ln(2)); if mi[l,t,1] if l<>x then begin t:=trunc(ln(x-l)/ln(2)); if mi[l,t,1] if r<>x then begin t:=trunc(ln(r-x)/ln(2)); if mi[x+1,t,1] o[ft,2]:=lt; o[ft,3]:=rt; o[lt,1]:=ft; o[rt,1]:=ft; dfs(l,x-1); dfs(x+1,r); end; procedure main; var i,b,t:longint; begin for i:=1 to n do mi[i,0,1]:=a[i,2]; for i:=1 to n do mi[i,0,2]:=i; for t:=1 to trunc(ln(n)/ln(2)) do for b:=1 to n-f[t]+1 do if mi[b,t-1,1]>mi[b+f[t-1],t-1,1] then mi[b,t]:=mi[b+f[t-1],t-1] else mi[b,t]:=mi[b,t-1]; dfs(1,n); end; procedure print; var i:longint; begin writeln('YES'); for i:=1 to n do writeln(o[i,1],' ',o[i,2],' ',o[i,3]); end; begin init; qsort(1,n); main; print; end. 程序1：（我一直用integer，搞得Running ERROR n次） var i,j,n:longint; k,a,b:array[0..50001] of longint; mn:array[0..50001,0..16] of longint; d:array[0..50001,1..3] of longint; procedure kp(l,r:longint); var x,y,z:longint; begin i:=l; j:=r; x:=k[i]; y:=a[i]; z:=b[i]; repeat while (i k[i]:=k[j]; a[i]:=a[j]; b[i]:=b[j]; inc(i); end; while (i k[j]:=k[i]; a[j]:=a[i]; b[j]:=b[i]; dec(j); end; until i>=j; k[i]:=x; a[i]:=y; b[i]:=z; if l procedure rmq1(n:longint); begin for i:=1 to n do mn[i,0]:=i; for i:=1 to trunc(ln(n)/ln(2)) do for j:=1 to n do begin mn[j,i]:=mn[j,i-1]; if j+(1<<(i-1))<=n then if a[mn[j,i]]>a[mn[j+(1<<(i-1)),i-1]] then mn[j,i]:=mn[j+(1<<(i-1)),i-1]; end; end; function rmq(l,r:longint):longint; var x:longint; begin x:=trunc(ln(r-l+1)/ln(2)); if a[mn[l,x]] else exit(mn[r-(1< 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] 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.