페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8258
서브태스크

소 병원 검진 1초 1024MB

문제

농부 존의 N (1≤N≤5⋅10^5) 마리의 소들이 일렬로 서 있으며, 소 1번이 줄의 맨 앞에, 소 N번이 줄의 맨 뒤에 있다. 농부 존의 소들은 여러 다른 종(species)으로 이루어져 있다. 그는 각 종을 1부터 N까지의 정수로 표시한다. 줄의 앞에서 i번째에 있는 소의 종은 a_i(1≤a_i≤N)다.

농부 존은 소들을 지역 소 병원에서 검진받게 하려 한다. 하지만 소 수의사는 매우 까다로워서, 줄의 i번째 소를 검진하려면 반드시 그 소가 종 b_i (1≤b_i≤N)이어야 한다.

농부 존은 게을러서 소들의 순서를 완전히 재배열하고 싶지 않다. 대신 그는 다음과 같은 연산을 딱 한 번 수행할 것이다.

두 정수 l과 r을 선택하여(1≤l≤r≤N), 줄의 l번째부터 r번째까지의 소들의 순서를 반대로 뒤집는다.

농부 존은 이 방법이 얼마나 효과적인지 측정하고 싶다.

가능한 모든 \frac{N\cdot(N+1)}2개의 연산에 대해, 검진받는 소들의 수의 합을 구하시오.


입력

첫 번째 줄에는 정수 N이 주어진다.

두 번째 줄에는 a_1, a_2,\ \cdots,\ a_N이 주어진다.

세 번째 줄에는 b_1, b_2,\ \cdots,\ b_N이 주어진다.


출력

첫 줄에 가능한 모든 연산에서 검진받는 소들의 수의 합을 출력한다.


부분문제

번호 점수 조건
#120점

N \le 100

#220점

N \le 5000

#320점

a_i,b_i는 [1,N] 범위의 랜덤한 수로 이루어져 있음.

#420점

a_i,b_i는 [1,2] 범위의 랜덤한 수로 이루어져 있음.

#520점

추가 제약 조건 없음


예제1

입력
3
123
123
출력
12

(l=1, r=1), (l=2, r=2), (l=3, r=3)을 선택하면 3마리의 소가 검진받음.

나머지 연산에서는 1마리씩 검진받음.

총 검진받는 소들의 수: 3 + 3 + 3 + 1 + 1 + 1 = 12


예제2

입력
7
1322132
3221231
출력
60

예제3

입력
3
132
321
출력
3

다음과 같은 연산을 수행할 수 있습니다.

(l=1, r=1), (l=2, r=2), (l=3, r=3)을 선택하면 줄의 순서가 바뀌지 않으므로 검진받는 소가 없습니다.

한 마리의 소가 검진받는 경우는 다음과 같습니다.

(l=1, r=2): 줄이 [3,1,2]가 되고 첫 번째 소가 검진받음.

(l=2, r=3): 줄이 [1,2,3]가 되고 두 번째 소가 검진받음.

(l=1, r=3): 줄이 [2,3,1]가 되고 세 번째 소가 검진받음.

총 검진받는 소들의 수: 0 + 0 + 0 + 1 + 1 + 1 = 3


출처

USACO 2025 January Silver

역링크