笛卡尔树
- 笛卡尔树
- 定义
- 构建
- 性质
- 习题
- P6453 [COCI 2008/2009 #4] PERIODNI
- CF1913D Array Collapse
- P4755 Beautiful Pair
- [ARC186B] Typical Permutation Descriptor
笛卡尔树
定义
笛卡尔树是一种二叉树,每一个节点由一个键值二元组 ( k , w ) (k,w) (k,w) 构成。要求 k k k 满足二叉搜索树的性质,而 w w w 满足堆的性质。如果笛卡尔树的 k , w k,w k,w 键值确定,且 k k k 互不相同, w w w 也互不相同,那么这棵笛卡尔树的结构是唯一的。
通俗的讲,笛卡尔树是一个二叉树,中序遍历是原序列,同时满足堆性质。
构建
以小根堆笛卡尔树为例。
法1
观察上图笛卡尔树,我们发现,一个节点的父亲就是 左边第一个比它小的 与 右边第一个比它小的 的较大的那个。
写个单调栈来回跑两遍即可。
法2
我们考虑将元素按下标顺序依次插入到当前的笛卡尔树中。那么每次我们插入的元素必然在这棵树的右链(右链:即从根节点一直往右子树走,经过的节点形成的链)的末端。于是我们执行这样一个过程,从下往上比较右链节点与当前节点 u u u 的 w w w,如果找到了一个右链上的节点 x x x 满足 w x < w u w_x<w_u wx<wu,就把 u u u 接到 x x x 的右儿子上,而 x x x 原本的右子树就变成 u u u 的左子树。
下图红框部分就是我们始终维护的右链:
模板P5854
cin>>n;for(int i=1;i<=n;i++){cin>>a[i];while(Sid&&a[S[Sid]]>a[i])Sid--;l[i]=S[Sid+1];if(Sid)r[S[Sid]]=i;S[++Sid]=i;S[Sid+1]=0;}
性质
- 区间 [ l , r ] [l,r] [l,r] 的极值所在为 l , r l,r l,r 在笛卡尔树上的 LCA。
- 每个数左右两边第一个比它大/小的数分别是它在笛
卡尔树上的父亲和“拐点祖先”。 - 随机笛卡尔树的树高是 O ( log n ) O(\log n) O(logn) 的。
习题
P6453 [COCI 2008/2009 #4] PERIODNI
1 ≤ n , k ≤ 500 1\le n,k\le 500 1≤n,k≤500,层高不会超过 1 0 6 10^6 106
考虑在第 i i i 列和第 j j j 列 的第 h h h 层都放了一个数,那么要求中间断开,即 min k = i j a i < h \min_{k=i}^j a_i <h mink=ijai<h,其中 a i a_i ai 为第 i i i 列层数。
考虑建出小根堆笛卡尔树。
分成了若干矩形,树形DP即可。
CF1913D Array Collapse
link
1 ≤ n ≤ 3 × 1 0 5 , 1 ≤ p i ≤ 1 0 9 1\le n\le 3\times 10^5,1\le p_i \le 10^9 1≤n≤3×105,1≤pi≤109
- 考虑建立一棵小根堆笛卡尔树。
- 每个子树的根节点对应一段区间 [ l , r ] [l,r] [l,r] 的最小值的位置 x x x。
- 左子树表示 [ l , x − 1 ] [l,x-1] [l,x−1],右子树表示 [ x + 1 , r ] [x+1,r] [x+1,r]。
- 记 f u f_u fu 表示以 u u u 为根(即区间 [ l , r ] [l,r] [l,r] )的方案数,也记为 f [ l , r ] f[l,r] f[l,r]。
- 如果不删除 u u u,方案为 f [ l , x − 1 ] × f [ x + 1 , r ] f[l,x-1] \times f[x+1,r] f[l,x−1]×f[x+1,r]。
- 考虑删除 u u u,因为是在笛卡尔树上 dp。
- 所以如果 l > 1 l>1 l>1,那么 u u u 可以被左边删掉,方案数为 f [ x + 1 , r ] f[x+1,r] f[x+1,r]。
- 同理 r < n r<n r<n,方案数为 f [ l , x − 1 ] f[l,x-1] f[l,x−1]。
- 如果都能被两边删除,算重的方案为 1 1 1(全部删掉)。
P4755 Beautiful Pair
link
1 ≤ n ≤ 1 0 5 , 1 ≤ a i ≤ 1 0 9 1\le n \le 10^5,1\le a_i\le 10^9 1≤n≤105,1≤ai≤109
- 考虑建立一棵大根堆笛卡尔树。
- 同上一题,每个子树的根节点对应一段区间 [ l , r ] [l,r] [l,r] 的最大值的位置 x x x。
- 类似分治,考虑计算跨过 x x x 的方案数。
- 枚举短的一边(不妨假设是左边),设 i ∈ [ l , x ] i\in[l,x] i∈[l,x],那么需要查询 [ x , r ] [x,r] [x,r] 内 ≤ a x a i \large \le \frac{a_x}{a_i} ≤aiax的数的个数。
- 容易证明枚举次数不超过 n log n n\log n nlogn次。
- 直接主席树维护即可。
[ARC186B] Typical Permutation Descriptor
link
1 ≤ N ≤ 3 × 1 0 5 , 0 ≤ A i < i 1\le N \le 3\times 10^5,0\le A_i< i 1≤N≤3×105,0≤Ai<i
不难发现 P A i P_{A_i} PAi 即是 i i i 左边第一个比 A i A_i Ai 小的数,根据这一点建立笛卡尔树,则原问题变为在笛卡尔树上填数的方案数,简单DP即可。