排序二叉树
题目描述
一个边长为 $n$ 的正三角形可以被划分成 $n^2$ 个小的边长为 $1$ 的正三角形,称为单位三角形。边长为 $3$ 的正三角形被分成三层共 $9$ 个小的正三角形,我们把它们从顶到底,从左到右以 $1\sim 9$ 编号,见下图。
![](https://cdn.luogu.com.cn/upload/image_hosting/mzls92cx.png)
四个这样的边长为 $n$ 的正三角形可以组成一个三棱锥。我们将正三棱锥的三个侧面依顺时针次序(从顶向底视角)编号为 $A,B,C$,底面编号为 $D$。侧面的 $A,B,C$ 号三角形以三棱锥的顶点为顶,底面的 $D$ 号三角形以它与 $A,B$ 三角形的交点为顶。
![](https://cdn.luogu.com.cn/upload/image_hosting/yyqpdocn.png)
其中 $\tt .$ 表示这个三角形面的 $1$ 号三角形位置,并依次编号下去。
上图为三棱锥展开后的平面图,每个面上标有圆点的是该面的顶,该图中侧面 $A,B,C$ 分别向纸内方向折叠即可还原成三棱锥。我们把这 $A,B,C,D$ 四个面各自划分成 $n^2$ 个单位三角形。
对于任意两个单位三角形,如有一条边相邻,则称它们为相邻的单位三角形。显然,每个单位三角形有三个相邻的单位三角形。现在,把 $1\sim 4n^2$ 里的所有整数分别随机填入四个面总共 $4n^2$ 个单位三角形中。
现在要求你编程求由单位三角形组成的最大二叉搜索树。所谓最大二叉搜索树,是指在所有由单位三角形组成的二叉搜索树中节点最多的一棵树。要求当 $i$ 作为二叉搜索树的一个节点时,$i$ 的儿子(如果有的话)和 $i$ 的父亲(如果有的话)必须与 $i$ 有邻边(三棱锥状态下的邻边,而非展开图的邻边)。
一棵二叉搜索树满足这个节点的左子树得每个值全部小于这个节点,这个节点的右子树的每个值全部大于这个节点。
输入输出格式
输入格式
输入的第一行为一个整数 $n$,表示展开图中每个面的三角形边长,也就是这个面有 $n^2$ 个单位三角形。
接下来每行 $n^2$ 个整数,一共四行,第一行表示 $A$ 面的单位三角形中填入的数,第二行表示 $B$ 面,以此类推。
输出格式
输出仅一行一个整数,表示最大二叉搜索树的节点个数。
输入输出样例
输入样例 #1
3
19 33 32 31 29 3 5 4 30
22 25 20 21 12 24 23 34 35
14 13 15 26 18 17 8 16 27
11 10 9 1 28 7 2 6 36
输出样例 #1
17
说明
### 样例解释
以下以 $A$ 面为例。记 $f(A,x)$ 表示 $A$ 面的第 $x$ 个单位三角形,以此类推。
$f(A,9)$ 与 $f(D,1)$ 有邻边,$f(A,7)$ 与 $f(D,2)$ 有邻边,$f(A,5)$ 与 $f(D,5)$ 有邻边。
$f(A,1)$ 与 $f(B,1)$ 有邻边,$f(A,4)$ 与 $f(B,2)$ 有邻边,$f(A,9)$ 与 $f(B,5)$ 有邻边。
$f(A,1)$ 与 $f(C,1)$ 有邻边,$f(A,2)$ 与 $f(C,4)$ 有邻边,$f(A,5)$ 与 $f(C,9)$ 有邻边。
以数字 $1$ 为二叉搜索树的根,可以得到节点最多的二叉搜索树为:
![](https://cdn.luogu.com.cn/upload/image_hosting/2y8i07id.png)
### 数据范围
对于 $100\%$ 的数据,$1\leqslant n\leqslant 18$,保证四个面所有单位三角形上填入的数互不相同且都取自 $[1,4n^2]$。