题目描述

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

题目分析

很显然答案就是B中的字母在A中的位置的序列的逆序对
那么 相同字母怎么办? 我们贪心的 让在B序列的位置相对靠后的字母 对应在A序列靠后的位置 减少逆序对数量
并且要开long long

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,num[28];
vector<int>sa[28];
char s[1000100],t[1000100];
int pos[1000100];
long long f[1000100],ans;
void update(int x) { for(;x;x-=x&-x) f[x]++; }
int ask(int x) { int sum=0; for(;x<=n;x+=x&-x) sum+=f[x]; return sum; }
int main()
{   
    scanf("%d",&n);
    scanf("%s%s",t+1,s+1);
    for(int i=n;i>=1;i--) 
        sa[s[i]-'A'+1].push_back(i);
    for(int i=n;i>=1;i--)
        pos[i]=sa[t[i]-'A'+1][num[t[i]-'A'+1]],num[t[i]-'A'+1]++;
    for(int i=1;i<=n;i++)
        ans+=ask(pos[i]+1),update(pos[i]);
    printf("%lld",ans);
    return 0;
}