P5149 会议座位 题解 归并排序 逆序对

会议座位

传送门

题目背景

话说���长最近很喜欢召开全校教职工大会，让老师们强行听他装逼

题目描述

现在校长在校园网上公布了一份座位表， n n n 位老师从左到右依次排成一行。老师们都对这个座位很满意。

然而到了开会时，校长不小心把座位表打乱了，老师们很不满。老师们并不在意自己的位置变了多少，但如果有一对老师 a a a 和 b b b，他们原来的座位是 a a a 在 b b b 左边，现在变成了 a a a 在 b b b 右边，那么这一对老师便会贡献一单位不满值。

校长想知道这些老师的总不满值是多少。

输入格式

第一行一个正整数 n n n，为 n n n 位老师。

第二行有 n n n 个字符串，每个字符串代表老师的名字（大小写敏感）。这一行代表原来的座位表。

第三行有 n n n 个字符串，代表打乱后的座位表。

输出格式

一行，一个正整数，表示老师们的总不满值。

样例 #1

样例输入 #1

3Stan Kyle KennyKyle Stan Kenny

样例输出 #1

1

样例 #2

样例输入 #2

5A B C D EB A D E C

样例输出 #2

3

提示

对于 30 % 30\% 30% 的数据， 1 ≤ n ≤ 1 0 3 1\le n \le 10^3 1≤n≤103。

对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 1 0 5 1\le n \le 10^5 1≤n≤105，每位老师名字长度不超过 5 5 5，只有大小写字母并且互不相同。注意名字对大小写敏感。

注明

以上来自洛谷 以上来自洛谷 以上来自洛谷

解题思路

温馨提示，建议你好好读题。 如果你还没思路，再往上看。

题目提到：

老师们并不在意自己的位置变了多少，但如果有一对老师 a a a 和 b b b，他们原来的座位是 a a a 在 b b b 左边，现在变成了 a a a 在 b b b 右边，那么这一对老师便会贡献一单位不满值。

由此可得，题目要求为，给你原始顺序序列以及打乱后的序列，求逆序对个数。不一样的是，将原本整型元素改为了字符串。

如果你不会逆序对求法，那么建议你先做这题。

AC Code

#includeusing namespace std;templateinline void Quick_Write(T x) {if (x  9) Quick_Write(x / 10);putchar(x % 10 + '0');return;}struct Project_String {string _string, a;} String[100005];int n;string a[100005], b[100005];long long Answer;inline void Merge_Sort(int left, int right) {if (left >= right) return;int middle = ((right - left) >> 1) + left;Merge_Sort(left, middle), Merge_Sort(middle + 1, right);int i = left, j = middle + 1, k = left;while (i if (a[i]