[CF1430E] String Reversal

题目

题目链接

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

思路

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

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

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

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

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

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

代码

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