题意

给定一个长度为 $n$ 的正整数序列 $\{a_{n}\}$，定义一次操作为交换两个相邻元素的位置，求将这个序列转换为非严格先递增后递减序列的最少操作步数。

数据范围：$n, a_i \in [1, 10^5]$

基本思路

用一个树状数组维护序列中的元素，从最小的元素开始枚举到左右两边需要移动的步数，选择步数较少的一边计入最终解，并将该元素从树状数组中移除。

C++ 代码

代码1（WA）

#include<bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 5;
long long n, x, c[N];
vector<long long> a[N];
long long ans;
long long lowbit(long long x) {
	return x & (-x);
}
void add(long long idx, long long d) {
	while (idx <= n) {
		c[idx] += d;
		idx += lowbit(idx);
	}
}
long long query(long long idx) {
	long long sum = 0;
	while (idx > 0) {
		sum += c[idx];
		idx -= lowbit(idx);
	}
	return sum;
}
int main() {
	scanf("%lld", &n);
	for (long long i = 1; i <= n; i++) {
		scanf("%lld", &x);
		a[x].push_back(i);
		add(i, 1);
	}
	for (long long i = 1; i < N; i++) {
		if (a[i].empty()) {
			continue;
		}
		for (long long j = 0; j < a[i].size(); j++) {
			n--;
			add(a[i][j], -1);
		}
		for (long long j = 0; j < a[i].size(); j++) {
			ans += min(n-query(a[i][j]), query(a[i][j]-1));
		}
	}
	printf("%lld\n", ans);
	return 0;
}

代码2（AC）

#include<bits/stdc++.h>
using namespace std;

const long long N = 1e5 + 5;
long long n, x, c[N];
vector<long long> a[N];
long long ans;

long long lowbit(long long x) {
	return x & (-x);
}

void add(long long idx, long long d) {
	while (idx <= n) {
		c[idx] += d;
		idx += lowbit(idx);
	}
}

long long query(long long idx) {
	long long sum = 0;
	while (idx > 0) {
		sum += c[idx];
		idx -= lowbit(idx);
	}
	return sum;
}

int main() {
	freopen("why.in", "r", stdin);
	freopen("why.out", "w", stdout);
	scanf("%lld", &n);
	for (long long i = 1; i <= n; i++) {
		scanf("%lld", &x);
		a[x].push_back(i);
		add(i, 1);
	}
	long long rst = n;
	for (long long i = 1; i < N; i++) {
		if (a[i].empty()) {
			continue;
		}
		for (long long j = 0; j < a[i].size(); j++) {
			rst--;
			add(a[i][j], -1);
		}
		for (long long j = 0; j < a[i].size(); j++) {
			ans += min(rst-query(a[i][j]), query(a[i][j]-1));
		}
	}
	printf("%lld\n", ans);
	return 0;
}

两个代码区别描述

代码2在代码1的基础上多定义了一个变量 rst 存储树状数组中剩余元素个数，并将后面循环体中的 n 改为了 rst 参与运算。

但是为什么只是换一个变量就能过了呢？请各路巨佬指点，拜谢。（如果有哪里描述不清楚还请指出，本蒟蒻可能语言表述能力一般）

:-)