[NOI2009] 二叉查找树 & 笛卡尔树学习笔记

这个题：二叉搜索树原理认识 + 区间dp；只要熟练相关算法就一定可以做出来。但我不行。。。

我们学习一下笛卡尔树：

什么垃圾东西，不学了。

发现这个题是 l 蓝书上一道题 jqb。

二叉查找树又有一个性质：二叉查找树的中序遍历是其代表的序列从小到大排序的结果。

而无论Treap如何旋转，其都是一棵二叉查找树，因此，无论我们怎么改变数的权值，这棵树的中序遍历还是不会变的。

所以假设 \(dp(l,r,x)\) 区间 \([l,r]\)，所有数的权值 >= \(x\) 的权值。

考虑二叉搜索树是怎么做区间 dp 的，枚举当前的根节点，然后加上的权值是当前区间 sum，表示新增的深度 1 * 权值。

复杂度 \(O(n^4)\)。