/ Vijos / 题库 /

最小交错

最小交错

时间限制:1秒  内存限制:256M


【题目描述】

 下有两排序列 \(A、B\),位置一一对用,两序列均为 \(1..N\) 的一个排列。当 \(A_i = B_j\) 时,上下会连一条边。你可以选择序列A或者序列B进行旋转任意K步,如 3 4 1 5 2 旋转两步为 5 2 3 4 1。求旋转后最小的相交的线段的对数。

【输入格式】

  第一行一个整数 \(N\)。
  接下来的 \(N\) 行,每行一个整数,表示序列 \(A\)
  再接下来的 \(N\) 行,每行一个整数,表示序列 \(B\)
  注意,序列 \(A\) 和 \(B\) 分别是 \(1..N\) 的排列。

【输出格式】

  输出一个整数,表示最小的相交线段对数。

【输入输出样例】

 Input

5
5
4
1
3
2
1
3
2
5
4

 Output

0

【数据限制】

  对于 \(100\%\) 的数据,\(1≤N≤100,000\)

【来源】

  Mr.he**

信息

ID
2590
难度
9
分类
数据结构 | 线段树 点击显示
标签
递交数
3
已通过
1
通过率
33%
上传者