CF1268C K Integers
Problem
给定 \(n\) 和一个 \(1\) 至 \(n\) 这 \(n\) 个数的排列 \(p_1,p_2,p_3,\dots,p_n\) 。定义一次操作可以交换 \(p\) 中相邻的两个数 \(p_i,p_{i+1}\)。定义函数 \(f\) ，\(f(k)\) 表示能使数列 \(p\) 中存在连续子序列 \(1,2,3,\dots,k\) 的最少操作次数。
求：\(f(1),f(2),f(3),\dots,f(n)\) 的值。\(n \le 2 \times 10^5\)。
Solution
首先，当 \(k = n\) 时，答案即为整个数列的逆序对数。
更一般地，
考虑 \(1\sim k\) 内的元素内部交换：消除逆序对。
考虑 \(1\sim k\) 中的元素与 $ > k$ 的元素进行交换：合并 \(1, 2, 3, \cdots, k\)。
所以可以分成这两个部分计算。
求消除逆序对的操作数，考虑每次在 \(pos_k\) 上加一，统计目前有多少个数的位置大于 \(pos_k\)。
求合并的操作数，考虑每一个 \(x > k\)，要么让它在 \((1, 2, 3, \cdots, k)\) 的左侧，要么在其右侧，因此最优操作数为 \(\min(s_{pos_x}, k - s_{pos_x})\)。
以上，\(pos_x\) 表示数 \(x\) 在原数列中出现的位置，\(s_i\) 表示位置 \(1\sim i\) 中小于 \(a_i\) 的数的数量。
然后会思考 \(\sum\limits_{x = k + 1}^{n}\min(s_{pos_x}, k - s_{pos_x})\) 的最小值怎么求，但如果就在这里吊死，那就死了
考虑原本的操作意义：把 \(1, 2, 3, \cdots, k\) 移到连续的位置，这个过程就是在向中间靠拢。（逆序对就可以让它们合在一起后再消掉）
不如二分一个中间点 \(mid\)，\(mid\) 左侧的数向右移，\(mid\) 右侧的数向左移，\(mid\) 从左到右，代价是先单增再单减的。
然后发现这个好做多了！因为所有数的初始位置之和可以树状数组求出（这里要另开一棵树状数组），而终止位置形成了 等差数列。
两者相减一下就可以得到操作数。
至于 \(mid\)，可知取 \(pos_1, pos_2, \cdots, pos_k\) 的中位数最优，这个可以直接在 树状数组上二分。
总时间复杂度可以做到 \(O(n\log{n})\)。
这个转成等差数列值得重视，实现细节也值得一看。（貌似之前没怎么写过树状数组上二分）
标签：Integers,pos,mid,cdots,CF1268C,逆序 From： https://www.cnblogs.com/Schucking-Sattin/p/17169595.html