[USACO17FEB] Why Did the Cow Cross the Road I P

# 题目描述 为什么牛要过马路？我们可能永远都不知道全部原因，但肯定的是，农民约翰的牛经常穿过马路。事实上，他们经常过马路，当他们的路径交叉时，他们经常碰到对方，这是约翰希望改进的情况。 农夫约翰将奶牛分成了$N$个不同的品种（$1\le N\le 100000$），他的每一个田地都是专门为一种特定的品种放牧; 例如，专门用于品种$12$奶牛的田地只能用于品种$12$的奶牛，而不能用于任何其他品种的奶牛。一条长长的路穿过他的农场。道路一侧有$N$个田地（每个品种一个），道路另一侧也有$N$个田地（每个品种也有一个）。所以，当一头牛穿过马路，它会穿过特定品种的两个田地。 如果农民约翰更仔细的研究他的计划，他会在道路两旁订购同品种田地，所以每个品种的两个田野将直接穿过彼此的道路。这样就可以让奶牛随意过马路，而不会有不同品种的牛碰撞在一起。唉，但现在道路两边的田地可能不一样，所以农民约翰明白，可能会有一对品种$(a,b)$是交叉的当且仅当是一对不同的品种，且道路上一边田地品种a上的任何路线都与道路另一边田地品种b的任何路线相交 。 农民约翰希望尽量减少品种的交叉对数。由于物流方面的原因，他表示，他可以在道路的一边移动牛，所以那边的田地可以“循环转移”。也就是说，对于一个给定的常值k来说，循环转移是指每头牧场里的牛都会向前移动k个田野，而最前面的k只奶牛会移动到最后，因为向前移动的奶牛已经填补了前k个田地。比如，如果道路一侧的田地移动前的排列为3,7,1,2,5,4,6，假设k为2，新排列将为4,6,3,7 ,1,2,5.请编程确定在道路一侧的田野适当循环移动后存在的品种交叉对的最小值。 # 输入格式 一行包含$N$ ($1 \leq N \leq 100,000$),接下来$N$行按顺序描述了小路一旁田地的品种的ID号，每一个ID号是一个在$1...N$之间的整数。倒数$N$行描述了小路另一旁田地的品种的ID号。 # 输出格式 循环移动道路侧的田野后，请输出可能的品种交叉对的最小数量（两边均可移动） 感谢@Adscn提供翻译@mydiplomacy修正

Why did the cow cross the road? We may never know the full reason, but it is certain that Farmer John's cows do end up crossing the road quite frequently. In fact, they end up crossing the road so often that they often bump into each-other when their paths cross, a situation Farmer John would like to remedy. Farmer John raises $N$ breeds of cows ($1 \leq N \leq 100,000$), and each of his fields is dedicated to grazing for one specific breed; for example, a field dedicated to breed 12 can only be used for cows of breed 12 and not of any other breed. A long road runs through his farm. There is a sequence of $N$ fields on one side of the road (one for each breed), and a sequence of $N$ fields on the other side of the road (also one for each breed). When a cow crosses the road, she therefore crosses between the two fields designated for her specific breed. Had Farmer John planned more carefully, he would have ordered the fields by breed the same way on both sides of the road, so the two fields for each breed would be directly across the road from each-other. This would have allowed cows to cross the road without any cows from different breeds bumping into one-another. Alas, the orderings on both sides of the road might be different, so Farmer John observes that there might be pairs of breeds that cross. A pair of different breeds $(a,b)$ is "crossing" if any path across the road for breed $a$ must intersect any path across the road for breed $b$. Farmer John would like to minimize the number of crossing pairs of breeds. For logistical reasons, he figures he can move cows around on one side of the road so the fields on that side undergo a "cyclic shift". That is, for some $0 \leq k < N$, every cow re-locates to the field $k$ fields ahead of it, with the cows in the last $k$ fields moving so they now populate the first $k$ fields. For example, if the fields on one side of the road start out ordered by breed as 3, 7, 1, 2, 5, 4, 6 and undergo a cyclic shift by $k=2$, the new order will be 4, 6, 3, 7, 1, 2, 5. Please determine the minimum possible number of crossing pairs of breeds that can exist after an appropriate cyclic shift of the fields on one side of the road.

The first line of input contains $N$. The next $N$ lines describe the order, by breed ID, of fields on one side of the road; each breed ID is an integer in the range $1 \ldots N$. The last $N$ lines describe the order, by breed ID, of the fields on the other side of the road.

Please output the minimum number of crossing pairs of breeds after a cyclic shift of the fields on one side of the road (either side can be shifted).

5
5
4
1
3
2
1
3
2
5
4

0