题解 P5149 【会议座位】
Baihua
2018-12-24 21:44:24
## 思路 ：求逆序对个数
* 字符串可以用$STL$中提供的$map$解决。
* 成功把字符串转化成数字序列$B$后，就可以利用**树状数组** 或者**归并排序** 求逆序对了 。
* 关于树状数组求逆序对的原理：
1. 对于任意的$B[i]$ ，$Add(B[i],1)$ 表示$B[i]$ 已经出现过。
2. $Ask(B[i]-1)$ 可以查找到那些**已经出现过** 的 ， 而且 **小于$B[i]$ ** 的数字的**个数** 。
3. 已经插入的$i-1$ 个数字里，有$i-1-Ask(B[i]-1)$ 个数大于$B[i]$ ，它们和$B[i]$ 构成了逆序对。
4. 累加答案即可
* 点击[这里](https://www.luogu.org/problemnew/show/P3374)学习树状数组
* Code
```cpp
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include <map>
#define re register
#define GC getchar()
#define Lowbit(X) (X&(-X))
using namespace std ;
const int Maxn = 100000 , Dlt = 1;
int N ;
struct Person {
int Place ;
string Name ;
};
Person A[Maxn + Dlt] ;
map <string , int > M ;
int B[Maxn + Dlt] ;
int T[Maxn + Dlt] ;
/*
头文件和准备工作
结构体Person 中的Place是原有的位置，Name是对应的字符串；
数组B是打乱的序列，T是树状数组。
*/
void Add (int X , int K) {
while (X <= N) {
T[X] += K ;
X += Lowbit(X) ;
}
}
int Ask (int X) {
int Ans = 0 ;
while (X > 0) {
Ans += T[X] ;
X -= Lowbit(X) ;
}
return Ans ;
}
//树状数组的添加和查询操作
int main () {
//freopen ("P5149.in" , "r" , stdin) ;
scanf ("%d" , &N) ;
M.clear();
for (re int i = 1 ; i <= N ; ++ i) {
cin >> A[i].Name ;
M[A[i].Name] = i ;
}
string S ;
for (re int i = 1 ; i <= N ; ++ i) {
cin >> S ;
B[i] = M[S] ;
}
// 利用map完成把字符串转化为数字的操作，方便后续树状数组的操作
memset (T , 0 , sizeof(T)) ;
long long int Ans = 0 ;
for (re int i = 1 ; i <= N ; ++ i) {
Add (B[i] , 1) ;
Ans += i - Ask(B[i] - 1) - 1 ;
}
cout << Ans<<endl;
fclose (stdin) ;
fclose (stdout);
return 0;
}
```
### Thanks!