﻿ 洛谷P3531 [POI2012]LIT-Letters - 鸿网互联

# 洛谷P3531 [POI2012]LIT-Letters

## 题目描述

Little Johnny has a very long surname.

Yet he is not the only such person in his milieu.

As it turns out, one of his friends from kindergarten, Mary, has a surname of the same length, though different from Johnny's.

Moreover, their surnames contain precisely the same number of letters of each kind - the same number of letters A, same of letters B, and so on.

Johnny and Mary took to one another and now often play together.

One of their favourite games is to gather a large number of small pieces of paper, write successive letters of Johnny's surname on them, and then shift them so that they obtain Mary's surname in the end.

Since Johnny loves puzzles, he has begun to wonder how many swaps of adjacent letters are necessary to turn his surname into Mary's. For a child his age, answering such question is a formidable task.

Therefore, soon he has asked you, the most skilled programmer in the kindergarten, to write a program that will help him.

## 输入输出格式

In the first line of the standard input there is a single integer  () denoting the length of Johnny's surname.

The second line contains Johnny's surname itself, i.e., contains its  successive letters (without spaces).

The third line contains Mary's surname in the same format: a string of  letters (with no spaces either).

Both strings consist only of capital (upper-case) letters of the English alphabet.

In tests worth 30% of points it additionally holds that .

Your program should print a single integer to the standard output: the minimum number of swaps of adjacent letters that transforms Johnny's surname into Mary's.

```3
ABC
BCA```

`2`

## 说明

1. A B \nA B 对于这种情况我们是不用进行交换的

2. A B \nB A 这种情况只需交换一次即可

1 2

2 1 此时2在1前，且2比1大(这不是废话么。。)

1.暴力，绝对TLE

2.归并排序

3.树状数组

### 多年oi一场空！！！！！！

``` 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #include<deque>
7 #include<queue>
8 #define LL long long
9 #define lb(x)    ((x)&(-x))
10 using namespace std;
11 const int MAXN=40000001;
12 inline int read()
13 {
14     char c=getchar();int x=0,f=1;
15     while(c<'0'||c>'9')    {if(c=='-')    f=-1;c=getchar();}
16     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
17 }
18 int n;
19 queue<int>q[28];
20 int a[MAXN];
21 int tree[MAXN];
22 inline void Point_Add(int pos,int val)
23 {
24     while(pos<=n)
25     {
26         tree[pos]+=val;
27         pos+=lb(pos);
28     }
29 }
30 inline int Interval_Sum(int pos)
31 {
32     int ans=0;
33     while(pos)
34     {
35         ans+=tree[pos];
36         pos-=lb(pos);
37     }
38     return ans;
39 }
40 int main()
41 {
43     for(int i=1;i<=n;i++)
44     {
45         char c=getchar();
46         q[c-'A'].push(i);
47     }
48     char c=getchar();// 可恶的换行符
49     for(int i=1;i<=n;i++)
50     {
51         char c=getchar();
52         a[i]=q[c-'A'].front();
53         q[c-'A'].pop();
54     }
55     LL ans=0;
56     for(int i=1;i<=n;i++)
57     {