相似题目：$Luogu$ $P1966$ 火柴排队
一些结论
首先看到交换相邻的，很容易能够想到逆序对。
接着再来看每个点都有确定的想要去的地方，那肯定是逆序对了呀！
有一个一眼可以看出的结论。
就是我们可以只调换终点相邻的，起点不调换。
或者只调换起点相邻的，重点不管。
证明很简单，相对性。
还有一个结论，为了消除交叉，最后一定是这种样子：
证明也很简单，反证法。
我们现在假如知道了一个航线的起点，那么我们就可以推出它的终点，比如样例：
$4$ 号航线的起点在第一个，那么终点也应该在第一个。
$2$ 号航线的起点在第二个，那么终点也应该在第二个。
构造目标数组
我们用 $l[i]$ 代表终点为 $i$ 的航线终点应该在哪，$l$ 数组很好搞。
输入起点的时候统计一个辅助数组 $c$，$c[i]$ 的意思是起点为第 $i$ 个的航线。
$c$ 数组在输入起点的时候可以完成。
然后输入终点时，假如当前输入的是 $x$，只需访问一下 $x$ 航线的起点。
$l[i]=c[x]$，这样 $l$ 数组就构造出来了，答案就是 $l$ 数组的逆序对数量，很好证明。
how to do it？
如果我们让 $l[i]=i$ 就是终点为 $i$ 的航线应该在 $i$，就完事儿了。
于是乎，现在要干的事儿就是交换 $l$ 数组里相邻的元素，使得 $l$ 升序排列。
所需要的最少步骤数就是该排列的逆序对数。
证明：在一个排列里交换两个相邻的元素，该排列的逆序对数量减一或加一。
逆序对有两个经典解法：树状数组，归并排序。
树状数组代码较为简洁，因为这题不需要离散化，所以我就贴一个树状数组的代码吧：
#include <iostream>
using namespace std;
long long n, x, ans;
int a[100005], b[100005], l[100005];
long long c[100005];
void add (int x){for (; x <= n; x += x & -x) ++ c[x];}
int query (int x){return x == 0 ? 0 : c[x] + query (x - (x & -x) );}
int main()
{
ios::sync_with_stdio (false);
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> x;
a[x] = i;
}
for (int i = 1; i <= n; i ++)
{
cin >> x;
l[i] = a[x];
}
for (int i = n; i >= 1; i --)
{
add (l[i]);
ans += query (l[i] - 1);
}
cout << ans << endl;
return 0;
}
标签：终点,交叉,int,五星级,航线,2021,数组,起点,逆序 From： https://www.cnblogs.com/Xy-top/p/16948986.html