0%

[CF1430E] String Reversal

题目

题目链接

题目大意:给出长度为 $n$ 的字符串,每次可以交换相邻两个字母,问至少要多少次操作能将字符串变为它的逆序。$2 \le n \le 200000$。

思路

如果没有重复字母的话,这道题就是 [NOIp2013] 火柴排队

但是现在是有重复元素的,所以需要进行一些改动。

大体思路依然一样,设 $c$ 为 $n$ 个元素的一个排列,且满足 $c_{a_i} = b_i$。

现在考虑相同字母应该怎么排,我们知道最后的答案为 $c$ 的逆序对个数,那只需要让 $c$ 尽量满足递增就可以让逆序对个数最小。

所以我们可以按照升序的顺序对相同字母进行操作,具体看代码吧。

最后求 $c$ 的逆序对个数即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef long long LL;

std::vector<int> v[30];
LL t[200010], a[200010], b[200010], c[200010], m[30];
LL ans;
int n;
char s[200010];

inline int lowbit(int x) { return x & -x; }

LL query(int x) {
LL s = 0;
while (x) {
s += t[x];
x -= lowbit(x);
}
return s;
}

void modify(int x, LL d) {
while (x <= n) {
t[x] += d;
x += lowbit(x);
}
return ;
}

int main() {
read(n);
scanf("%s", s + 1);
for (int i = 1; i <= n; ++i) {
a[i] = s[i] - 'a' + 1;
b[n - i + 1] = a[i];
}
for (int i = 1; i <= n; ++i) v[b[i]].push_back(i);
for (int i = 1; i <= n; ++i) c[i] = v[a[i]][m[a[i]]++];
for (int i = 1; i <= n; ++i) {
modify(c[i], 1);
ans += i - query(c[i]);
}
printf("%lld\n", ans);
return 0;
}