一道关于逆序对的题目。
乍一看，字母不好处理，因此以一开始方块排列的情况作为标准从1~n标号，然后按这个编号给方块的目标排列情况标号。如下所示：
R G B -> G B R
1 2 3 -> 2 3 1
若字母相同，就要使开始和目标方块的编号差距尽量小，这样，才能使操作次数最少（小小的贪心）。如下所示：
A A C B -> B A C A
1 2 3 4 -> 4 1 3 2
（若目标方块的编号为4 2 3 1，则最小操作数为5）
把问题转化一下：给定一无序列，通过交换相邻元素使该序列变为有序列的最少交换次数。
这不就是求该无序列的逆序对的数量吗？
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
证明（逆序对数==最小交换次数）：
以4 1 3 2为例
第一步，将最大的数字放到最后，即将大数与小数交换位置，并把大数交换到最后面，得到1 3 2 4，这一步共进行了3次交换操作；
第二步，将最大的数字删去，得到1 3 2，重复第一步，得到1 2 3，这一步共进行了一次交换操作。
得到有序列后，将操作次数相加，正好是逆序对的个数。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
接下来就好办了，代码很好写。
写代码的过程中，还有一个问题就是如何给字母编号。有一个笨办法就是下面代码中的注释，利用数组存位置；另外一个聪明的办法与笨办法的思想类似，但是用的是队列存位置：给每一个字母一个队列，遇到一次该字母就将其位置入队，遍历目标字母序列式时，只需要访问相应字母的队首位置并将其出列。
**总结：
1.通常字母要转化成数字处理。
2.无序列中，逆序对的个数==最小交换次数。
#include<iostream>#include<cstdio>#include<queue>#define N 1000100#define ll long longusing namespace std;ll Tree[N];queue<ll>pos[30];char st[N],en[N];ll g(char x){return x-'A'+1;}ll Lowbit(ll x){return x&(-x);}void Add(ll x){if(!x)return;for(ll i=x;i<N;i+=Lowbit(i))Tree[i]++;}ll get(ll x){if(!x)return 0;ll Ans=0;for(ll i=x;i;i-=Lowbit(i))Ans+=Tree[i];return Ans;}int main(){ll n;scanf("%lld",&n);scanf("%s%s",st+1,en+1);for(ll i=1;i<=n;i++){ll t=g(st[i]);pos[t].push(i);}ll Ans=0;for(ll i=1;i<=n;i++){ll tmp=g(en[i]);ll t=pos[tmp].front();pos[tmp].pop();Add(t),Ans+=get(n)-get(t);}printf("%lld",Ans);return 0;}
