#P2789. [Poi2012]Letters

    ID: 1897 传统题 1000ms 512MiB 尝试: 690 已通过: 374 难度: 4 上传者: 标签>CF1600普及+/提高-同字符有序匹配求最少相邻交换次数树状数组鸣谢oimaster

[Poi2012]Letters

题目描述

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

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

输入格式

第一行一个正整数 nn,表示字符串的长度。 第二行和第三行各一个长度为 nn 的字符串,并且只包含大写英文字母。

输出格式

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

3
ABC
BCA
2

样例说明

ABC→BAC→BCA\text{ABC}\to\text{BAC}\to\text{BCA}。

数据规模与约定

对于 100%100\% 的数据,1≤n≤1061\leq n\leq 10^6,字符串只包含大写英文字母。