笛卡尔树是个神仙东西。
神仙出了两道相关的题目，两道题目都巧妙地运用了笛卡尔树的优异性质。
这里总结一下关键的内容。
假设有排列 ，表示 的权值为 。
笛卡尔树，权值上满足堆的性质，而节点编号满足二叉搜索树的性质。
对于一棵小根笛卡尔树，我们考虑树上的节点 。对于 到根的路径，我们把每条向右的边都与向左的边交换，可以得到一条从根到 的左链。换言之，我们先求出每一条从根到 的左链的方案数，那么我们一定可以通过交换路径上的左右边来涵盖所有的笛卡尔树——也就是涵盖所有的排列情况。
接下来，我们考虑对所有的排列形成的笛卡尔树计数。
链是没有形态一说的，我们只要考虑链的深度就行了。设根的深度为 ， 表示考虑前 个点，第 个点深度为 的左链方案数。考虑转移，枚举 的父节点 ，因为是小根笛卡尔树，所以 一定小于 ，则：
初值设为 。
大概就是除去 ，剩下的 个数中选出来 个是小于 的，这部分的方案数在 中，其余的数在序列中必须摆在 的右边，任意排列即可。
考虑从左链扩展到全树。设 表示第 个点，深度为 的笛卡尔树的方案数。则：
大概就是每一层都可以选择换/不换，比 大的数我们可以插入已经确定的位置内任意排列。
于是我们确定了任意排列的情况下，笛卡尔树上每一个数每一个深度的方案数。对于贡献可以分开计算的题目而言，暴力就可以直接做了。
复杂度 。