题目大意

给定长度为 $n$ 的一个序列，将其分割为若干段。每一段的贡献是这一段的逆序对个数加上 $k$，求出所有段的贡献的和的最小值。

数据范围满足，$1\le n\le 3\times 10^5$。

思路

设 $V(l,r)$ 表示 $[l,r]$ 这个区间的贡献，因为要做到动态查询 $[l,r]$ 的逆序对在 Ynoi 上的做法是分块，带一个 $\sqrt{n}$ 很难过，所以考虑只处理需要。

发现逆序对有一个很优美的性质，那就是在一个序列的前面或者后面新添加一个元素，可以用树状数组来做到 $\log V$ 添加新元素同时计算贡献。

所以我们希望询问的 $V(l,r)$ 的 $l,r$ 都是大部分都是连续的，发现分治的做法刚好满足这个要求。

但是分治做法需要满足转移分层，也就是转移方程与以前的 DP 值没有关系，这个题目显然不满足这个要求，考虑写一个 CDQ 来转移。

之所以写一个 CDQ 是因为 CDQ 有一个特点，就是计算贡献的时候左区间的 $f$ 总时已经求解出来了，也就是可以满足 $\text{solve}(l,r,x,y)$ 的 $[1,l)$ 里的 $f$ 都已经求解完成了，这样转移即使不满足转移的分层也可以写分治做法。

时间复杂度是 $O(n\log^3 n)$，这 $3$ 个 $\log$ 分别来自 CQD、分治和树状数组。

因为这 $3$ 个玩意的常数都很小，而且题目开了 $5$ 秒的时限，所以 zjk 实测用 $3.5$ 秒就过了。

似乎正解有一个可持久化数组的做法，时间复杂度是 $O(n\sqrt{n}+n\log^2 n)$，但是我不会。