P9843 [ICPC2021 Nanjing R] Paimon Sorting 题解 （SPJ）

[ICPC2021 Nanjing R] Paimon Sorting

传送门

题面翻译

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

// 排序算法
SORT(A)
  for i from 1 to n // n 是序列 A 的元素个数
    for j from 1 to n
      if a[i] < a[j] // a[i] 是序列 A 的第 i 个元素
        Swap a[i] and a[j]

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

题目描述

Paimon just invents a new sorting algorithm which looks much like $\text{bubble?sort}$, with a few differences. It accepts a $1$-indexed sequence $A$ of length $n$ and sorts it. Its pseudo-code is shown below.

// The Sorting Algorithm
SORT(A)
  for i from 1 to n // n is the number of elements if A
    for j from 1 to n
      if a[i] < a[j] // a[i] is the i-th element in A
        Swap a[i] and a[j]

If you don’t believe this piece of algorithm can sort a sequence it will also be your task to prove it. Anyway here comes the question:

Given an integer sequence $A=a_1,a_2,?,a_n$ of length $n$, for each of its prefix $A_k$ of length $k$ (that is, for each $1\le k\le n$, consider the subsequence $A_k=a_1,a_2,?,a_k$), count the number of swaps performed if we call $\text{SORT}(A_k)$.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1\le n\le 10^5$) indicating the length of the sequence.

The second line contains $n$ integers $a_1,a_2,?,a_n$ ($1\le a_i\le n$) indicating the given sequence.

It’s guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

输出格式

For each test case output one line containing $n$ integers $s_1,s_2,?,s_n$ separated by a space, where $s_i$ is the number of swaps performed if we call $\text{SORT}(A_i)$.

Please, DO NOT output extra spaces at the end of each line or your solution may be considered incorrect!

样例 #1

样例输入 #1

3
5
2 3 2 1 5
3
1 2 3
1
1

样例输出 #1

0 2 3 5 7
0 2 4
0

$以上由米哈游赞助$（注意题目标题：Paimon？）

解题思路

分类讨论

• 对于每个长度的第一轮循环之后，结果是将其严格单增序列相对位置后移，之后第 $2,3\dots$ 轮排序的交换次数就是前 $i$ 个比 $a_i$ 大的个数，该操作有去重效果。 因此为了获得最后的解，在扫描的时候可以直接处理，保证每次只获得当前长度下第一次循环的结果，当遇到 $a_i>a_1$ 时，就交换 $a_i$ 和 $a_1$ 的位置，这就是一次必要的交换，计数器增加 $1$，然后对于每个在线处理输入的 $a_i$，统计先前比它大的个数，直接加上即可。 但是，当录入的 $a_i$ 与 $a_1$ 相等（$a_1$ 为当前最大值）（设值为 $x$）并且后面存在比 $a_1$ 更大的数（设值为 $y$），那么在后面的长度当中，第一轮排序会使得当前的 $a_i$ 的值不变，而 $a_1$ 对应的值被移到了更大的数位置上，（形象一些就是这样：$x,x,y\to y,x,x$）那么在插入 $y$ 之后，由于 $y$ 向前移动了，$y$ 对 $x$ 也有一个需要交换的贡献，举例如下，假设当前长度构造的序列为：$x,a,a,a,x,x?1,x?2,x?1$，那么插入 $y$ 之后，由于 $y$ 大于 $x$，则变为了：$y,a,a,a,x,x?1,x?2,x?1,x$。那么对于 $x,x?1,x?2,x?1$ 这几个数，都需要加上 $y$ 与 $y$ 的这个贡献，所以需要增加一个计数器（cnt），记录第二个 $x$ 到 $y$ 间有几个数，插入 $y$ 的时候结果加上计数器值即可。
• 对于序列所有元素各不相同的情况，首先从第一个元素开始，找到并跳到当前元素右边第一个比它大的元素。称这些元素为“特殊元素”。可以发现外层循环的第一轮会把所有特殊元素右移一位，此时序列中最大的元素就到了序列第一个。
  从外层第二轮循环开始，对于第 $i$ 轮循环，序列前 $(i?1)$ 个元素已经是有序的。设此时第一个比 $a_i$ 大的元素是 $a_k$? ，那么第 $i$ 轮循环将会发生 $(i?k)$ 次交换。因此，非特殊元素将会贡献“前面有几个数比它大”次交换，但一开始特殊元素的右移对答案没有影响，因为虽然移走了一个比它大的元素，但是最大的元素移到了开头，而特殊元素将会贡献 $2$ 次交换。
• 对于存在相同元素的情况，对非特殊元素，前面比它大的，但是相同的元素只会发生一次交换，因此需要对元素去重一下再统计。另外，如果这个非特殊元素恰好等于上一个特殊元素，那么上一个特殊元素的右移会导致该非特殊元素的贡献加 $1$。

这么长题解不想看？那就给我看完。

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn = 1e5 + 5;
int n, a[Maxn];
int Tree[Maxn];
bool vis[Maxn];
inline int lowbit(int x) {
	return x & (-x);
}
inline void Add(int x) {
	for (int i = x; i <= n; i += lowbit(i)) {
		Tree[i]++;
	}
}
inline int Sum(int x) {
	int tot = 0;
	for (int i = x; i; i -= lowbit(i)) {
		tot += Tree[i];
	}
	return tot;
}
inline void solve() {
	memset(Tree, 0, sizeof(Tree));
	memset(vis, 0, sizeof(vis));
	cin >> n;
	int res = 0, cnt = 0;
	bool flag = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	cout << 0;
	vis[a[1]] = 1;
	Add(a[1]);
	for (int i = 2; i <= n; i++) {
		if (!vis[a[i]]) {
			vis[a[i]] = 1;
			Add(a[i]);
		}
		if (a[i] == a[1]) {
			flag = 1;
		}
		cnt += flag - (flag ? a[i] > a[1] : 0);
		if (a[i] > a[1]) {
			res += cnt + 1;
			swap(a[1], a[i]);
			cnt = flag = 0;
		}
		res += Sum(a[1]) - Sum(a[i]);
		cout << " " << res;
	}
	cout << endl;
}
inline void work() {
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	work();
	return 0;
}