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

#8257
서브태스크

FJ는 게으르지만, 소들은 검사를 받아야 해! 1초 1024MB

문제

Farmer John의 소 N마리 (1 ≤ N ≤ 7500)는 일렬로 서 있다. 맨 앞에 있는 소는 1번 소, 맨 뒤에 있는 소는 N번 소이다. FJ의 소들은 여러 종(Species)으로 이루어져 있으며, 각 소의 종은 1부터 N까지의 정수로 표현된다. i번째 소의 종을 a_i라고 할 때, 주어진 배열 a = [a_1, a_2, ..., a_N]은 소들의 초기 배치를 나타낸다.

FJ는 소들을 가축 병원(bovine hospital)으로 데려가야 한다. 그런데 수의사는 매우 까다로워서, i번째 소가 검사받으려면 그 소의 종이 b_i여야 한다. 즉, 주어진 배열 b = [b_1, b_2, ..., b_N]은 각 위치에서 검사받아야 할 소의 종을 나타낸다.

FJ는 소들을 완전히 재정렬하는 것을 싫어한다. 그래서 다음과 같은 한 번의 연산만 수행할 수 있다.

  • 두 개의 정수 (l, r)를 선택한다. 구간 [l, r]에 해당하는 소들의 순서를 뒤집는다. 즉, 소들의 위치를 l번부터 r번까지 반전시킨다.

이 작업을 통해 b와 최대한 많은 소들의 종이 일치하도록 만들려고 한다.

FJ는 이 방법이 얼마나 효과적인지 측정하고 싶어 한다. 따라서 c = 0부터 N까지, c마리의 소가 검사받을 수 있도록 만드는 (l, r) 선택 방법의 개수를 구하는 프로그램을 작성하라.

두 연산 (l₁, r₁)과 (l₂, r₂)가 다르다는 것은 다음과 같다.

  • l₁ ≠ l₂ 또는 r₁ ≠ r₂이면 서로 다른 연산이다.


입력

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

두 번째 줄에 N개의 정수 a₁, a₂, ..., aₙ이 주어진다.

세 번째 줄에 N개의 정수 b₁, b₂, ..., bₙ이 주어진다.


출력

N+1개의 줄을 출력해야 한다.

i번째 줄에는 (i-1)마리의 소가 검사받을 수 있도록 하는 연산 (l, r)의 개수를 출력한다.


부분문제

번호 점수 조건
#130점

N \le 100

#270점

추가 제약 조건 없음


예제1

입력
3
132
321
출력
3
3
0
0

(검사받을 수 있는 소가 0마리인 경우)

  • (1,1), (2,2), (3,3) → 이 경우, 배열이 바뀌지 않으므로 검사받을 수 있는 소가 없다. (3개)

(검사받을 수 있는 소가 1마리인 경우)

  • (1,2) → 배열: [3,1,2] → 첫 번째 소가 검사받을 수 있다.

  • (2,3) → 배열: [1,2,3] → 두 번째 소가 검사받을 수 있다.

  • (1,3) → 배열: [2,3,1] → 세 번째 소가 검사받을 수 있다.

검사받을 수 있는 소가 2마리 이상인 경우는 불가능하므로, 0을 출력한다.


예제2

입력
3
123
123
출력
0
3
0
3

(검사받을 수 있는 소가 3마리인 경우)

  • (1,1), (2,2), (3,3) → 배열이 변하지 않으므로 모든 소가 검사받을 수 있다.


예제3

입력
7
1322132
3221231
출력
0
6
14
6
2
0
0
0

(검사받을 수 있는 소가 4마리인 경우)

  • (4,5) → 배열: [1,3,2,1,2,3,2]

  • (5,7) → 배열: [1,3,2,2,2,3,1]

    • 이 두 경우만 가능하다.


출처

USACO 2025 January Bronze

역링크