题目链接：会议座位 - 洛谷
题目背景
话说校长最近很喜欢召开全校教职工大会，让老师们强行听他装逼
题目描述
现在校长在校园网上公布了一份座位表，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
题解：
明显求逆序对，不过转化了一种形式，为字符串的逆序对。考虑用map离散化后哈希到数组中，转化为熟悉的归并排序求逆序对。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);inline int read()
{int x=0,k=1; char c=getchar();while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*k;
}
const int maxn=1e5+10;
int b[maxn],n,a[maxn],ans;
map<string,int>m;
string s;
void mergesort(int l,int r){if(l>=r) return ;int mid=(l+r)>>1;mergesort(l,mid);mergesort(mid+1,r);int i=l,j=mid+1,k=l;while(i<=mid&&j<=r){if(a[i]<a[j])b[k++]=a[i++];elseb[k++]=a[j++],ans+=mid-i+1;}while(i<=mid){b[k++]=a[i++];}while(j<=r){b[k++]=a[j++];}for(int i=l;i<=r;i++) a[i]=b[i];
}
signed main(){fastcin>>n;for(int i=1;i<=n;i++){cin>>s;m[s]=i;}for(int i=1;i<=n;i++){cin>>s;a[m[s]]=i;}//离散化，用map哈希。mergesort(1,n);cout<<ans;
}