Note - 一些东西
我们来进行一些学习：
数据结构：
笛卡尔树
定义：
- 树上每个节点都是一个二元组 ，只看 ，笛卡尔树是一棵二叉查找树；只看 ，笛卡尔树是一棵二叉小根堆。
性质：
-
如果 递增，笛卡尔树可以 求得（单调栈维护右链）。
-
如果 互不相同， 互不相同，笛卡尔树唯一。
例题：
-
P5854 【模板】笛卡尔树 —— 模板。
-
P1377 [TJOI2011] 树的序 —— 键值满足二叉查找树性质，时间满足小根堆性质，故以 建笛卡尔树就可以建成题目所要求的树。再观察发现，对于每一颗子树，根节点必须先于左右儿子，左儿子先于右儿子比右儿子先于左儿子更加划算，故输出树的先序遍历即可。
算法：
搜索练习题：
-
P1979 [NOIP2013 提高组] 华容道 —— 挺有意思的一道题，而且思维难度和码量都不算大，主要算法为 和最短路。
-
先观察题目可以发现，如果想让目标棋子移动，那么空白棋子必须在其相邻位置，所以我们拿到一个询问要干的第一件事情肯定是把空白棋子移动到目标棋子旁边，这个过程可以用 在 的时间内解决。
-
如果想让目标棋子向某一方向移动，需要让空白棋子移动到那一方向的相邻棋子。我们可以发现，棋子在棋盘上的状态只有 种，相邻棋子只有四种，一个方向到另一个方向的种类最多有 种，故可以预处理，对于每个状态进行 ,可以在 的时间内解决。
-
接下来只需要让目标棋子通过旋转和位移用最少步数走到目的地。但这个时候边权不再为定值，不可 。不难发现只有 条边，故对每一次询问都跑一次 即可，可在 的时间内解决。
-
总时间复杂度 。
Dijkstra & bellman_ford & SPFA求单源最短路径