CF 1269E. K Integers（结论题，树状数组）

传送门

求出现 1 , 2 , … , k 1,2,dots,k 1,2,…,k的操作数。

1. 数字必须连续，结论是向中位数靠拢。
2. 使排列恢复有序，想到冒泡，操作为求逆序对数目。

#include 
using namespace std;

#include 
#include 
__gnu_pbds::tree,
                  __gnu_pbds::rb_tree_tag,
                  __gnu_pbds::tree_order_statistics_node_update>
    tr;

int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n; cin >> n;
  vector pos(n + 1);
  vector bit(n + 1, 0);
  for (int x, i = 1; i <= n; i++) {
    cin >> x, pos[x] = i;
  }
  auto add = [&](int p, long long v) {
    for (; p <= n; p += p & -p) bit[p] += v;
  };
  auto query = [&](int p) {
    long long res = 0;
    for (; p; p &= p - 1) res += bit[p];
    return res;
  };
  long long inv = 0, sum = 0;
  for (int i = 1; i <= n; i++) {
    tr.insert(pos[i]), add(pos[i], pos[i]), sum += pos[i];
    long long ans = inv += (long long) i - 1 - tr.order_of_key(pos[i]);
    long long mid, sl, sr, cl, cr;

    if (i & 1) {
      mid = *tr.find_by_order((i - 1) / 2);
      cl = (i - 1) / 2 + 1, cr = i - cl;
    } else {
      mid = (*tr.find_by_order(i / 2) + *tr.find_by_order(i / 2 - 1)) / 2;
      cl = i / 2, cr = i - cl;
    }
    sl = query(mid), sr = sum - sl;

    ans += cl * (mid + mid - cl + 1) / 2 - sl;
    ans += sr - cr * (mid + 1 + mid + cr) / 2;
    cout << ans << " n"[i == n];
  }
  return 0;
}