Cow Checkups

题目描述

农夫约翰有 $N$ 头奶牛（$1 \leq N \leq 5 \cdot 10^5$）站成一排，奶牛 $1$ 在队首，奶牛 $N$ 在队尾。FJ 的奶牛有许多不同的品种。他用从 $1$ 到 $N$ 的整数表示每个品种。队列中从前往后第 $i$ 头奶牛的品种是 $a_i$（$1 \leq a_i \leq N$）。 FJ 要带奶牛去当地的牛医院体检。然而兽医非常挑剔，只会给队列中第 $i$ 头奶牛体检，当且仅当它的品种为 $b_i$（$1 \leq b_i \leq N$）。 FJ 很懒，不想完全重排奶牛。他将恰好进行一次如下操作。 选择两个整数 $l$ 和 $r$，满足 $1 \leq l \le r \leq N$。将队列中第 $l$ 头到第 $r$ 头（含）奶牛的顺序反转。 FJ 想衡量这种方法的效果。请计算在所有 $N(N+1)/2$ 种可能操作中，被兽医体检的奶牛数量之和。

输入格式

第一行包含一个整数 $N$。 第二行包含 $a_1, a_2, \ldots, a_N$。 第三行包含 $b_1, b_2, \ldots, b_N$。

输出格式

输出一行：在所有可能操作中，被兽医体检的奶牛数量之和。

3
1 3 2
3 2 1

3

3
1 2 3
1 2 3

12

7
1 3 2 2 1 3 2
3 2 2 1 2 3 1

60

提示

如果 FJ 选择 ($l=1,r=1$)、($l=2,r=2$) 或 ($l=3,r=3$)，则不会有奶牛被体检。注意这些操作不会改变奶牛的位置。 以下操作会导致恰好有一头奶牛被体检。 $l=1,r=2$：FJ 反转第 1 头和第 2 头奶牛的顺序，因此新队列中各奶牛的品种为 $[3,1,2]$。第 1 头奶牛会被体检。 $l=2,r=3$：FJ 反转第 2 头和第 3 头奶牛的顺序，因此新队列中各奶牛的品种为 $[1,2,3]$。第 2 头奶牛会被体检。 $l=1,r=3$：FJ 反转第 1、2、3 头奶牛的顺序，因此新队列中各奶牛的品种为 $[2,3,1]$。第 3 头奶牛会被体检。 在全部六种操作中，被体检的奶牛总数为 $0+0+0+1+1+1=3$。 有三种可能的操作会导致有 $3$ 头奶牛被体检：($l=1,r=1$)、($l=2,r=2$) 和 ($l=3,r=3$)。其余操作每个都会导致有 $1$ 头奶牛被体检。在全部六种操作中，被体检的奶牛总数为 $3+3+3+1+1+1=12$。 SCORING: Input 4: $N\le 100$ Input 5: $N\le 5000$ Inputs 6-9: $a_i, b_i$ 均在区间 $[1,N]$ 内均匀随机生成 Inputs 10-15: $a_i, b_i$ 均在区间 $[1,2]$ 内均匀随机生成 Inputs 16-23: 无额外限制。 题目贡献者：Chongtian Ma, Haokai Ma, and Alex Liang

标签: USACO|2025|Silver

来源

USACO|2025|Silver