算法
(贪心、树状数组) $O(n\log n)$
假设 $t$ 为 $s$ 通过交换交换相邻字符变成的结果字符串,可以把 $t$ 当成原始串,然后找到 $s$ 中每个字符的在原始串中的位置,其构成 $(1,2,3, \cdots, n)$ 的某个排列。
显然我们不需要改变相同字符的相对顺序,否则操作次数一定会增加
比如 s = icpcsguru
t = urugscpci
p_t = (123456789)
s = icpcsguru
p_s = (967854123)
我们的目标就是把 $s$ 变成 $t$,这等价于把 $p_s$ 变成 $p_t$,而这显然是求逆序对的问题,再考虑到 $n$ 为 $2e5$,那我们可以用树状数组来维护。此外,我们还需要开栈数组来维护相同字符的位置顺序。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::stack;
using std::vector;
using std::string;
using ll = long long;
stack<int> st[26];
template<typename T>
struct BIT {
int n;
vector<T> d;
BIT(int n=0):n(n),d(n+1) {}
void add(int i, T x=1) {
for (i++; i <= n; i += i&-i) {
d[i] += x;
}
}
T sum(int i) {
T x = 0;
for (i++; i; i -= i&-i) {
x += d[i];
}
return x;
}
T sum(int l, int r) {
return sum(r-1) - sum(l-1);
}
};
int main() {
int n;
string s;
cin >> n >> s;
rep(i, n) st[s[i] - 'a'].push(i);
ll ans = 0;
BIT<int> t(n);
rep(i, n) {
int p = st[s[i] - 'a'].top();
st[s[i] - 'a'].pop();
ans += t.sum(p);
t.add(p);
}
cout << ans << '\n';
return 0;
}