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,cdots,a_n

$A = a_{1}, a_{2}, \dots, a_{n}$ 的所有前缀

⋯

A_k=a_1,a_2,cdots,a_k

$A_{k} = a_{1}, a_{2}, \dots, a_{k}$ （

≤

1le kle n

$1 \leq k \leq n$ ），

SORT

⁡

(

)

operatorname{SORT}(A_k)

$SORT (A_{k})$ 中的交换（Swap）操作将会被执行几次。

题目描述

Paimon just invents a new sorting algorithm which looks much like

bubble

sort

textit{bubble sort}

$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, cdots, a_n

$A = a_{1}, a_{2}, \dots, a_{n}$ of length

$n$ , for each of its prefix

A_k

$A_{k}$ of length

$k$ (that is, for each

≤

1 le k le n

$1 \leq k \leq n$ , consider the subsequence

⋯

A_k = a_1, a_2, cdots, a_k

$A_{k} = a_{1}, a_{2}, \dots, a_{k}$ ), count the number of swaps performed if we call

SORT

(

)

text{SORT}(A_k)

$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

$1 \leq n \leq 1 0^{5}$ ) indicating the length of the sequence.

The second line contains

$n$ integers

⋯

a_1, a_2, cdots, a_n

$a_{1}, a_{2}, \dots, a_{n}$ (

≤

1 le a_i le n

$1 \leq a_{i} \leq n$ ) indicating the given sequence.

It’s guaranteed that the sum of

$n$ of all test cases will not exceed

10^6

$1 0^{6}$ .

输出格式

For each test case output one line containing

$n$ integers

⋯

s_1, s_2, cdots, s_n

$s_{1}, s_{2}, \dots, s_{n}$ separated by a space, where

s_i

$s_{i}$ is the number of swaps performed if we call

SORT

(

)

text{SORT}(A_i)

$SORT (A_{i})$ .

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

样例 #1

样例输入 #1

样例输出 #1

0 2 3 5 7
0 2 4
0

以上由米哈游赞助

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

解题思路

分类讨论

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

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

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;
}