#PU1470. USACO 2025 January Contest, Silver — Problem 1. Cow Checkups

USACO 2025 January Contest, Silver — Problem 1. Cow Checkups

USACO 2025 January Contest, Silver — Problem 1. Cow Checkups

题目描述

Farmer John's NN (1≤N≤5⋅1051 \leq N \leq 5 \cdot 10^5) cows are standing in a line, with cow 11 at the front of the line and cow NN at the back of the line. FJ's cows also come in many different species. He denotes each species with an integer from 11 to NN. The ii'th cow from the front of the line is of species aia_i (1≤ai≤N1 \leq a_i \leq N). FJ is taking his cows to a checkup at a local bovine hospital. However, the bovine veterinarian is very picky and wants to perform a checkup on the ii'th cow in the line, only if it is species bib_i (1≤bi≤N1 \leq b_i \leq N). FJ is lazy and does not want to completely reorder his cows. He will perform the following operation exactly once . Select two integers ll and rr such that 1≤l≤r≤N1 \leq l \le r \leq N. Reverse the order of the cows that are between the ll-th cow and the rr-th cow in the line, inclusive. FJ wants to measure how effective this approach is. Find the sum of the number of cows that are checked by the veterinarian over all N(N+1)/2N(N+1)/2 possible operations.

输入格式

The first line contains an integer NN. The second line contains a1,a2,…,aNa_1, a_2, \ldots, a_N. The third line contains b1,b2,…,bNb_1, b_2, \ldots, b_N.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
1 3 2
3 2 1
3
If FJ chooses ($l=1,r=1$), ($l=2,r=2$), or ($l=3,r=3$) then no cows will be
checked. Note that those operations do not modify the location of the cows.
The following operations result in one cow being checked.
$l=1,r=2$: FJ reverses the order of the first and second cows so the species
of each cow in the new lineup will be $[3,1,2]$. The first cow will be checked.
$l=2,r=3$: FJ reverses the order of the second and third cows so the species
of each cow in the new lineup will be $[1,2,3]$. The second cow will be checked.
$l=1,r=3$: FJ reverses the order of the first, second, and third cows so the
species of each cow in the new lineup will be $[2,3,1]$. The third cow will be
checked.
The total number of cows checked over all six operations is $0+0+0+1+1+1=3$.

样例 2

3
1 2 3
1 2 3
12
There are three possible operations that cause $3$ cows to be checked:
($l=1,r=1$), ($l=2,r=2$), and ($l=3,r=3$). The remaining operations each result
in $1$ cow being checked. The total number of cows checked over all six
operations is $3+3+3+1+1+1=12$.

样例 3

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