Description:

刚开始你有 $n$ 个序列长度都为 $1$ ，每次支持拼接两个序列，问每个序列的每个子区间的最小值的和。

$1\leqslant n\leqslant 10^6$

Solution：

有单调栈做法，但十分复杂。

询问子区间最小值，可以想到笛卡尔树，那么答案就是每个节点的权值乘上左右子树大小之积，也就是说我们如果能在均摊复杂度下合并笛卡尔树的话，就可以把那些因为合并而发生变化的点特殊统计一下，其他的点的贡献不变。

笛卡尔树也是一棵 $treap$ ，但是如果用 $fhq\_treap$ 的合并方法的话因为优先级不随机所以可以卡成 $O(n^2)$ ，但是实际上有一个不受权值影响的线性合并做法，考虑 $fhq\_treap$ 的合并方法，显然只有 $treap$ 最靠左或者最靠右的那一条链会发生变化，我们称在最靠左或者最靠右的那一条链上的点为特殊点，假设第一个堆的根节点的权值小于第二个点的，那么最终合并的形式应该是把第一个堆的右儿子和第二个堆合并，直到某个右儿子的权值大于第二个点，然后再把这个点这个子树和第二个笛卡尔树递归合并，但是这样可能每次都遍历整个右链，发现递归合并之后第一棵树的剩下那些右链以后就不再是最右边的链了，因此我们可以从下往上找，也就是对每棵笛卡尔树维护左链和右链的端点，然后从下往上找最后一个满足条件的位置，然后把这棵子树和另一棵笛卡尔树像无旋 $treap$ 那样直接合并，因为剩下暴力合并经过的点一定都是关键点，每次合并一定经过两次一些关键点（一次查找一次合并），并且这些关键点在之后都不再是关键点，因此复杂度是严格的均摊 $O(n)$ 。

Code：

没有代码