Descirption

给出一个排序算法（用伪代码表示）：

SORT(A)
  for i from 1 to n
    for j from 1 to n
      if a[i] < a[j]
        Swap a[i] and a[j]

算出对于一个序列 \(A=a_1,a_2,\cdots,a_n\) 的所有前缀 \(A_k=a_1,a_2,\cdots,a_k\)（\(1\le k\le n\)），\(\operatorname{SORT}(A_k)\) 中的交换（Swap）操作将会被执行几次。

Solution

Part I

考虑对于如何计算整个序列的答案。

先模拟第一次循环，交换该交换的。

观察发现，从第二次循环开始，当外层循环枚举到 \(i\) 时，\([1,i-1]\) 已经排好序了，并且 \(a_{i-1}\) 是全局最大值。此时可能交换的 \(j\) 一定在 \([1,i-1]\) 中，具体地，这次交换会交换 \(\sum_{j=1}^{i-1}[a_j>a_i]\) 次。

因为 \(j<i\)，所以 \(i\) 和 \(j\) 交换不会影响之后的次数，树状数组维护 \(\sum_{j=1}^{i-1}[a_j>a_i]\) 即可。

REP(k, 1, n) {
	Fenwick<int> T(n); vector<int> p(n + 1), t(n + 1);
	int cnt = 0; 
	REP(i, 1, k) p[i] = a[i];
	REP(i, 1, k)
		if (p[1] < p[i]) swap(p[1], p[i]), cnt ++;
	REP(i, 1, k) {
		cnt += T.ask(n) - T.ask(p[i]);
		if (!t[p[i]]) T.upd(p[i], 1), t[p[i]] = 1;
	}
	cout << cnt << " \n"[k == n];
}

Part II

考虑在原来算出答案的序列 \(\{a_{n}\}\) 最后加入一个数 \(k\)。

我们设 \(t=\max\{a_{i}\}\)。

如果 \(k\leq t\)，那么对第一次循环没有影响，正常二维数点即可。

如果 \(k>t\)，那么第一次循环时会把原来在 \(a_1\) 的 \(t\) 放到最后，然后把 \(a_1\) 改成 \(k\)。设原序列中 \(t\) 第二次出现在 \(p\)。对于 \([1,p-1]\) 中的数，把 \(t\) 拿走又加入 \(k\)，交换次数不变。对于 \([p,n]\) 中的数，因为前面的 \(t\) 不止一个，加入 \(k\) 后 \(t\) 仍然有贡献，每个位置的交换次数都会加 \(1\)。

简单维护即可。

Fenwick<int> T(n);
vector<int> vis(n + 1);
LL res = 0, p = 0, cnt = 0;
REP(i, 1, n) {
	if (!vis[a[i]]) T.upd(a[i], 1), vis[a[i]] = 1;
	if (i > 1 && a[i] == a[1]) p = 1;
	if (a[1] < a[i])
		res += cnt + 1, cnt = p = 0, swap(a[1], a[i]);
	cnt += p, res += T.ask(n) - T.ask(a[i]);
	cout << res << " \n"[i == n];
}