P5149 会议座位（逆序对 离散化 hash 归并排序）
题目链接：会议座位 - 洛谷
题目背景
话说校长最近很喜欢召开全校教职工大会，让老师们强行听他装逼
题目描述
现在校长在校园网上公布了一份座位表，n 位老师从左到右依次排成一行。老师们都对这个座位很满意。
然而到了开会时，校长不小心把座位表打乱了，老师们很不满。老师们并不在意自己的位置变了多少，但如果有一对老师 a 和 b，他们原来的座位是 a 在 b 左边，现在变成了 a 在 b 右边，那么这一对老师便会贡献一单位不满值。
校长想知道这些老师的总不满值是多少。
输入格式
第一行一个正整数 n，为 n 位老师。
第二行有 n 个字符串，每个字符串代表老师的名字（大小写敏感）。这一行代表原来的座位表。
第三行有 n 个字符串，代表打乱后的座位表。
输出格式
一行，一个正整数，表示老师们的总不满值。
输入输出样例
输入
3Stan Kyle KennyKyle Stan Kenny
输出
1
输入
5A B C D EB A D E C
输出
3
题解：
明显求逆序对，不过转化了一种形式，为字符串的逆序对。考虑用map离散化后哈希到数组中，转化为熟悉的归并排序求逆序对。
#includeusing 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'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;mapm;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>n;for(int i=1;i>s;m[s]=i;}for(int i=1;i>s;a[m[s]]=i;}//离散化，用map哈希。mergesort(1,n);cout<<ans;}
