新高一暑假第一期集训新课【笛卡尔树】(补)
B. Beautiful Pair
如果构建一棵笛卡尔树的话那么两个点之间的 \(max\) 就在笛卡尔树的 \(\operatorname{LCA}\) 位置。
所以对于每个位置维护一个线段树，然后每次暴力枚举小的那棵子树在大子树的线段树中查询即可。然后线段树合并或者启发式合并上去就好了。
建笛卡尔树的时候用 \(\operatorname{RMQ}\) 查询区间最大值然后递归下去就好了。
时间复杂度 \(\Theta (n\log^2 n)\)。
注意 \(1\) 要特判就好了。
C. [51NOD1934] 受限制的排列
去找最小的那个数，最小的数的 \(l\) 和 \(r\) 应该就是 \(1\) 和 \(n\)。
因为这是一个排列，我们把问题从最小值处 \(p\) 分开，得到两个一样的问题 \((1, p - 1)\) 和 \((p + 1, n)\)。
设区间长度为 \(len\)，分出的两个区间长度为 \(len_l\) 和 \(len_r\)，贡献就是这两个问题的答案的积乘上 \(\displaystyle\dbinom{len - 1}{len_l}\)。
找最小值直接用 map 暴力存下来就好了。时间复杂度 \(\Theta(n \log n)\)。
好像没用到笛卡尔树诶
D. [AGC028B] Removing Blocks
这类求 所有情况的代价，都可以这样求：随机一个排列，求代价的期望 \(\times\) 情况数。
考虑计算每个元素在一个固定顺序中，贡献到代价中的次数。
建立基于删除时间的小根堆笛卡尔树，则笛卡尔树上一个节点对答案的贡献是字数内 \(a_i\) 之和。
设 \(h_i\) 是 \(i\) 号点的贡献，令根节点深度为 \(1\)，则代价之和为 \(\displaystyle\sum\limits_{i = 1}^n h_i \times a_i\)。
考虑一个排列：若 \(x \lt i\) 且 \(x\) 是 \(i\) 的祖先，则 \(x,x + 1, \dots, i - 1\) 都应该比 \(i\) 后删除，这样的方案数占总方案数的 \(\displaystyle\frac{(i - x)!}{(i - x + 1)!} = \frac{1}{i - x + 1}\)。
因为只有这 \(i - x + 1\) 个元素的相对顺序是重要的，其中恰好有 \(\displaystyle\frac{1}{i - x + 1}\) 个排列满足 \(i\) 在最前面被删除。
同理 \(x\gt i\)，有 \(\displaystyle\frac{1}{x - i + 1}\) 的概率成立。
对于每一个 \(x\lt i\)，\(x \gt i\)，都可以有这样的概率，因此有：
\[E(h_i) = \sum_{x = 1}^{i - 1} \frac{1}{i - x + 1} + \sum_{x = i + 1}^n \frac{1}{x - i + 1} + 1 \]设 \(\displaystyle s_x = \sum_{i = 1}^x \frac{1}{i}\)，则 \(E(h_i) = s_i + s_{n - i + 1} - 1\)，因此答案为：
\[ans = n! \times \sum_{i = 1}^n (s_i + s_{n -i + 1} - 1) \times a_i \]按式计算即可。
标签：frac,笛卡尔,sum,新课,len,集训,times,displaystyle From： https://www.cnblogs.com/Leirt/p/18528919