10.12 模拟赛

题解

A. 选择排序

粘过来题面的代码：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++)
        if (a[i] < a[j])
            swap(a[i], a[j]);
}

考虑如何计算整个串的答案。

首先暴力做一遍 \(i = 1\)。此时序列中的最大值一定会被交换到 \(a_1\)。

然后将刚才的答案加上目前 \(a\) 中的逆序对数量就是真实答案。具体的，我们需要对于每个 \(j\)，计算 \(j\) 之前有多少种数 \(> a_j\)。

为啥？模拟+找规律。

for (int x = 1; x <= n; ++ x ) {
	for (int i = 1; i <= x; ++ i ) a[i] = b[i];
	
	int res = 0;
	for (int j = 1; j <= x; ++ j ) {
		if (a[1] < a[j]) {
			swap(a[1], a[j]);
			res ++ ;
		}
	}
	
	for (int i = 2; i <= x; ++ i ) res += /* i 前面有多少种数 > a[i] */;
	
	cout << res << " \n"[x == n];
}

用树状数组实现可以做到整体 \(\mathcal O(n^2)\) 的复杂度。现在考虑优化上面的代码。

for (int x = 1; x <= n; ++ x ) {
	for (int i = 1; i <= x; ++ i ) a[i] = b[i];
	
	int res = 0;
    
    // 优化这个循环比较简单。注意到从 x -> x+1 时，我们只需要在上一次的基础上多做一次 j = x+1 即可。
	for (int j = 1; j <= x; ++ j ) {
		if (a[1] < a[j]) {
			swap(a[1], a[j]);
			res ++ ;
		}
	}
    // 也就是说，从 x -> x+1 时 a[1 ~ x] 中至多只会有 a[1] 会发生变化，其他位置一定不会发生改变
	
    // 别忘了每次上面的循环结束后，a[1] 都是目前的最大值
    // 我们知道当枚举的是 x 时 a[1] 是最大值。那么当枚举的变成 x+1 时，如果上面 j = x+1 的没有执行（即 a[x + 1] < a[1]，即 a[1] 仍然是最大值），那么前面所有数对答案的贡献都没有发生改变。
    // 否则，由于 a[1] 可能会出现多次，考虑下面的图。先我们即将将第一个位置从 a[1] 变成 a[x + 1]，且 a[x + 1] > a[i]
    // 显然绿色区间内的数对答案的贡献没有变化。因为 a_1 本来就比它们大，而我们是把 a_1 替换成一个更大的数。
    // 但是蓝色区间内的数对答案的贡献会增加 1。这是因为原先它们前面有两个 a_1，但是我们只计算了一个的贡献。现在我们把其中一个 a_1 改变了，也就是说原来的两个数现在都要贡献一次，所以这些数的贡献会大 1。
	for (int i = 2; i <= x; ++ i ) res += /* i 前面有多少种数 > a[i] */;
	
	cout << res << " \n"[x == n];
}

所以我们需要维护一种数据结构，支持查询某种数字在序列中第一次和第二次的出现位置，以及删除第一个数。双端队列（deque）或链表（list）即可。

加上树状数组总复杂度 \(\mathcal O(n \log n)\)。