RiseOJ – 소 건강검진

설명

농부 존의 소 $$N$$ 마리( $1 \leq N \leq 5 \cdot 10^5$ )가 한 줄로 서 있다. 소 $$1$$ 이 줄의 맨 앞에, 소 $$N$$ 이 줄의 맨 뒤에 있다. 농부 존의 소들은 여러 품종으로 이루어져 있으며, 각 품종은 $$1$$ 부터 $$N$$ 까지의 정수로 나타낸다. 줄의 앞에서 $$i$$ 번째 소의 품종은 $$a_i$$ ( $1 \leq a_i \leq N$ )이다.

농부 존은 소들을 데리고 지역 소 병원에 건강검진을 받으러 간다. 하지만 수의사는 매우 까다로워서, 줄에서 $$i$$ 번째에 있는 소가 품종 $$b_i$$ ( $1 \leq b_i \leq N$ )일 때에만 그 소를 검진하려고 한다.

농부 존은 게을러서 소들을 완전히 재배치하고 싶지 않다. 그는 다음 연산을 정확히 한 번 수행한다.

$1 \leq l \le r \leq N$ 을 만족하는 두 정수 $$l$$ 과 $$r$$ 을 선택한다. 줄에서 $$l$$ 번째 소부터 $$r$$ 번째 소까지(양 끝 포함)의 순서를 뒤집는다.

농부 존은 이 방법이 얼마나 효과적인지 측정하고 싶다. 가능한 $$N(N+1)/2$$ 가지 연산 각각에 대해 수의사가 검진하는 소의 수를 모두 더한 값을 구하시오.

Problem credits: Chongtian Ma, Haokai Ma, and Alex Liang

제약

배점

입력 4: $N\le 100$
입력 5: $N\le 5000$
입력 6-9: $$a_i, b_i$$ 는 모두 $$[1,N]$$ 범위에서 균등하게 무작위로 생성된다
입력 10-15: $$a_i, b_i$$ 는 모두 $$[1,2]$$ 범위에서 균등하게 무작위로 생성된다
입력 16-23: 추가 제약이 없다.

Problem credits: Chongtian Ma, Haokai Ma, and Alex Liang

입력 형식

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

둘째 줄에 $a_1, a_2, \ldots, a_N$ 이 주어진다.

셋째 줄에 $b_1, b_2, \ldots, b_N$ 이 주어진다.

출력 형식

가능한 모든 연산에 대해 수의사가 검진하는 소의 수를 모두 더한 값을 한 줄에 출력한다.

예제 1

입력

3
1 3 2
3 2 1

출력

설명

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

출력

설명

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

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > January > Silver

올림피아드 > USACO > 2024-2025 > January > Silver

태그

JudgeUSACO

소 건강검진

평가 및 의견

풀이 제출