笛卡尔树
panyf
·
·
个人记录
笛卡尔树是一棵二叉树，每个点有两种权值 (k,w)，要求 k 满足二叉搜索树的性质，w 满足堆的性质。
容易发现 k 互不相同并且 w 互不相同时，笛卡尔树的结构唯一。
模板题：P5854 【模板】笛卡尔树
构建：
假设所有点已经按 k 排好序。
$O(n)$ 构建：
考虑按 $k$ 从小到大插入每个点，用栈维护从根开始一直走右儿子形成的链。插入一个点 $i$ 时，弹栈顶直到栈空或者 $w_{top}<w_i$，将最后一个弹出的点作为 $i$ 的左儿子（若不存在则没有左儿子）。然后若栈不为空，则将 $i$ 作为栈顶的右儿子。最后将 $i$ 加入栈。
[#424. 【集训队作业2018】count](https://uoj.ac/problem/424)
首先特判掉 $n<m$，输出 $0$。
考虑序列对应的笛卡尔树，根据题目中最大值的定义，左子树的权值必须小于根，右子树的权值只需要小于等于根。对于两个序列，若笛卡尔树相同，则同构。考虑怎样的笛卡尔树是合法的，容易发现从根到任何一个结点的路径上，经过的左儿子数量必须小于 $m$，否则 $m$ 个数就不够用了。容易发现 $m$ 个数必须都出现的限制没用，当 $n\geq m$ 时通过一个出现了 $m-1$ 个数的序列很容易构造出一个出现了 $m$ 个数的同构序列。所以左儿子数量小于 $m$ 是充要条件。
定义 $f(root)$ 为一个括号序列，且 $f(root)=(f(lson))f(rson)$，不存在的结点为空。容易发现长度为 $2n$ 的合法括号序列和 $n$ 个点的二叉树一一对应。合法的笛卡尔树就对应一个嵌套层数不超过 $m$ 的括号序列。于是问题转化为：从 $(0,0)$ 走到 $(2n,0)$，只能走右上或右下，不经过 $y=-1$ 和 $y=m+1$ 的方案数。
没有任何限制，从 $(0,0)$ 走到 $(x,y)$ 的方案数是 $C_x^{(x+y)/2}$，记为 $p(x,y)$。若只有一个限制，比如 $y=-1$，则将起点关于 $y=-1$ 对称得到 $(0,-2)$，从 $(0,-2)$ 到 $(2n,0)$ 的路径和不合法路径一一对应（考虑对不合法路径，将起点到第一次碰到 $y=-1$ 的一段关于 $y=-1$ 对称，就得到一个 $(0,-2)$ 到 $(2n,0)$ 的路径），于是答案为 $p(2n,0)-p(2n,2)$。
考虑有两个限制怎么做。考虑一种方案，先碰到 $y=-1$，就加入一个 a，再碰到 $y=m+1$，就加入一个 b，以此类推，每种方案都可以表示成 ababab... 或者 bababa... 的形式。考虑枚举一个 ab 交替的串，求包含这个串的方案数，以 aba 为例，先将 $(0,0)$ 关于 $y=-1$ 对称，然后关于 $y=m+1$ 对称，然后再关于 $y=-1$对称，即为当前点到 $(2n,0)$ 的方案数。然后再容斥，对于一个 ab 串，容斥系数为 $-1$ 的串长次方。时间复杂度 $O(n)$。
[#410. 【IOI2018】会议](https://uoj.ac/problem/410)
考虑笛卡尔树上分治。对于每个结点，记其子树区间为 $[l,r]$，求出所有前缀区间 $[l,i]$ 的答案和后缀区间 $[i,r]$ 的答案。对于一组询问，找到跨过的结点 $i$，用左区间的后缀答案和右区间的前缀答案合并即可。
考虑如何求前后缀区间的答案。假设当前结点为 $m$，左区间 $[l,m-1]$，右区间 $[m+1,r]$。对于 $i\geq m$，区间 $[l,i]$ 的答案就是 $\min(ans(l,m-1)+(i-m+1)\times h_m,ans(m+1,i)+h_m\times(m-l+1))$。容易发现 $\min$ 中两部分的差是单调的，可以二分找到分界点，前半部分相当于区间赋值成等差数列，后半部分相当于区间加，线段树维护即可。区间 $[i,r]$ 同理。$O(n\log n)$。