//https://codeforces.com/problemset/problem/1430/e

題意

已知一個小寫字母字符串A，現(xiàn)有一個A的翻轉(zhuǎn)字符串B，每次可以交換A中兩個相鄰的字母，問至少交換多少次可以得到字符串B。

思路

設(shè)字符串A為aabbc，則字符串B為cbbaa。

貪心考慮，枚舉字符串B中的字符，每次優(yōu)先選擇字符串A中最近的相同字符交換過來。

接下來需要維護最近的相同字符的貢獻。

1. 首先用26個雙端隊列，保存26的字母出現(xiàn)的每個位置。對于B串的第一個字符c，在A串中的位置為5，要將字符c交換至第一個位置，

那么字符串A中位置1至4的字符都要后移一位。

2. 前面匹配完成的字符已經(jīng)不會再產(chǎn)生貢獻，因此可以看成該字符被刪除，

而單個字符移動所需要的花費就是兩個字符之間存在的字符數(shù)量。

3. 如果從A串中的最后一個字符開始向前處理，則位置pos的字符貢獻，即是位置pos前剩余的字符個數(shù)。與位置pos后面的字符沒有關(guān)系。

可以用樹狀數(shù)組維護。

input

9

icpcsguru