【bzoj2789】letters

2014年11月11日1,7860

Description

给出两个长度相同且由大写英文字母组成的字符串A、B,保证A和B中每种字母出现的次数相同。

现在每次可以交换A中相邻两个字符,求最少需要交换多少次可以使得A变成B。

Input

第一行一个正整数n (2<=n<=1,000,000),表示字符串的长度。

第二行和第三行各一个长度为n的字符串,并且只包含大写英文字母。

Output

一个非负整数,表示最少的交换次数。

Sample Input

3
ABC
BCA

Sample Output

2

HINT

ABC -> BAC -> BCA

题解

cxjyxxw_me:

这题一定对于某个字母

一定是贪心的把离它最近的字母移过来
这样就可以对A串标出1~n的排列的一个序
对这个序求逆序对数即为ans