关于这篇题解中的分治复杂度的分析。

因为 $\log$ 可以预处理，暂且不算作者调用 $\log$ 所带来的多的一个 $\log$ 。作者后面的分治的时间复杂度写的是 $\mathcal{O}(\log^2 n)$ 。

为了算最大时间复杂度，把 $minpos$ 和 $maxpos$ 都看成一个点，显然就是算一个递归式子 $f(l,r)=f(l,x)+f(x+1,r)\ (l\leq x < r)$ 的复杂度，其中 $f(x,x)$ 和合并的复杂度都是 $O(1)$。不太会时间复杂度证明的我理解为把 $f(1,1),f(2,2)...f(n,n)$ 从底向上合并在一起，显然这个复杂度是 $\mathcal{O(n)}$ 的。事实证明我的分治做法中会被单调递减的一组数据卡成 $O(n)$ 。

可是这篇题解的做法却说是 $\mathcal{O}(\log^2 n)$，我尝试构造一组可以让每次递归时 $minpos$ 和 $maxpos$ 都相等的一组数据从而变成 $\mathcal{O}(n)$ 的复杂度，却完全不知道该怎么构造，所以这篇题解的复杂度究竟为多少？又是怎么分析出来的呢？