CF EDU 96 E - String Reversal

贪心、逆序对

E - String Reversal

题意

给一个长度为 n 的字符串 s，(n <= 2e5), 把 s 反转后的字符串记为 s', 每次只可以交换相邻两个字符，求把 s 变为 s' 的最小次数

思路

1. 可以从左到右枚举 s，对于当前位置 i，字符 a 要变成 字符 b，则较靠前的 a 要去给较靠前的 b 匹配（没有必要把原串的第 1 个 ch 作为目标串的最后 1 个 ch，而是也作为第 1 个），这样移动次数一定是最优的

   具体可以用 二维vector 存下每个字符的位置，G[ch] 为字符 ch 的所有位置，且位置按升序排列

   对于每个 G[ch] 再 reverse 一下，位置按逆序排列

   从 1 到 n 枚举位置 i 要变成的字符，其实就是从 n 到 1 枚举原字符串，设当前枚举的字符是 ch，就是找 G[ch].back(), 再弹出即可

2. 这样就找到了每个位置 i 与之匹配的位置

   在这个数组中求逆序对就是答案（类似冒泡排序最小次数就是逆序对个数）

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;
#define endl "\n"

typedef long long ll;
typedef pair<int, int> PII;

const int N = 2e5 + 10, M = 27;
int n;
int a[N], tr[N];
vector<vector<int> > G(M);

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

int sum(int idx)
{
	int ans = 0;
	for (int i = idx; i; i -= lowbit(i))
		ans += tr[i];
	return ans;
}

void add(int idx, int k)
{
	for (int i = idx; i <= n; i += lowbit(i))
		tr[i] += k;
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		char x;
		cin >> x;
		a[i] = x - 'a' + 1;
		G[a[i]].push_back(i);
	}
	for (int i = 1; i < M; i++)
		reverse(G[i].begin(), G[i].end());

	ll ans = 0;
	for (int i = n; i >= 1; i--)
	{
		int v = G[a[i]].back();
		// cout << v << endl;
		G[a[i]].pop_back();
		ans += sum(n) - sum(v-1);
		add(v, 1);
	}
	cout << ans << endl;
    return 0;
}