【题目来源】
https://www.luogu.com.cn/problem/P5149
【题目描述】
话说校长最近很喜欢召开全校教职工大会。现在校长在校园网上公布了一份座位表，n 位老师从左到右依次排成一行。老师们都对这个座位很满意。
然而到了开会时，校长不小心把座位表打乱了，老师们很不满。老师们并不在意自己的位置变了多少，但如果有一对老师 a 和 b，他们原来的座位是 a 在 b 左边，现在变成了 a 在 b 右边，那么这一对老师便会贡献一单位不满值。
校长想知道这些老师的总不满值是多少。
【输入格式】
第一行一个正整数 n，为 n 位老师。
第二行有 n 个字符串，每个字符串代表老师的名字（大小写敏感）。这一行代表原来的座位表。
第三行有 n 个字符串，代表打乱后的座位表。
【输出格式】
一行，一个正整数，表示老师们的总不满值。
【输入样例一】
3
Stan Kyle Kenny
Kyle Stan Kenny
【输出样例一】
1
【输入样例二】
5
A B C D E
B A D E C
【输出样例二】
3
【数据范围】
对于 30% 的数据，1≤n≤10^3。
对于 100% 的数据，1≤n≤10^5，每位老师名字长度不超过 5，只有大小写字母并且互不相同。注意名字对大小写敏感。
【算法分析】
● 本题就是在求逆序对，只不过将“洛谷 P1177：【模板】排序”中的数字换成了本题中的字符串。“洛谷 P1177：【模板】排序”的代码详见：https://blog.csdn.net/hnjzsyjyj/article/details/145693691
● 注意：ans 类型设为 long long。否则，只能得 60 分。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int maxn=1e5+5;
int a[maxn],t[maxn];
map<string,int> mp;
string s;
long long ans;
int n;void merge_sort(int le,int ri) {if(le==ri) return;int mid=(le+ri)>>1;merge_sort(le,mid);merge_sort(mid+1,ri);int p=le;int i=le,j=mid+1;while(i<=mid && j<=ri) {if(a[i]<a[j]) {t[p++]=a[i++];ans=ans+j-mid-1;} else t[p++]=a[j++];}while(i<=mid) {t[p++]=a[i++];ans=ans+j-mid-1;}while(j<=ri) t[p++]=a[j++];for(int i=le; i<=ri; i++) a[i]=t[i];
}int main() {cin>>n;for(int i=1; i<=n; i++) {cin>>s;mp[s]=i;}for(int i=1; i<=n; i++) {cin>>s;a[mp[s]]=i;}merge_sort(1,n);cout<<ans<<endl;return 0;
}/*
in:
5
A B C D E
B A D E Cout:
3
*/【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/145693691
https://blog.51cto.com/u_13536312/5371438
https://blog.csdn.net/hnjzsyjyj/article/details/145679752