CF1268C K Integers

发表于 分类于 ， ， 阅读次数：

题意：给出长为 的排列，每次可以交换相邻两个位置。

设 为使排列中存在连续子序列 的最少操作次数。

求出 。

，时限 。

最优方案可以分为两步：

  • 把 以最少的交换次数移动到一个连续区间内。在最优方案中，它们的相对位置不会改变。
  • 花费他们的逆序对的代价，整理成有序的形式。

我们可以分别考虑两步的开销。

按照 的顺序依次求解。

  • 逆序对

    加入数字 的时候，代价增加后面小于自己的数（即已经加入的数）的个数。

    线段树维护即可。

  • 移动代价

    代价是所有要收集的点到应该到的位置的距离。

    形式化地，我们如果要收集的位置为 ，目标位置是 ，则总代价是 这是一个经典的模型。把 看做数轴上的点， 的意义就是选定一个点使得其到所有点的距离和最小。

    结论：取 为 的中位数。

    对 维护权值线段树，即可快速求中位数，以及代价之和。

复杂度 。