P9261 [PA 2022] Canvas

**This problem is translated from [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Round 4 [Płótno](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/plo/).** Because of Christmas, Bytie received a large canvas from his parents. The canvas is divided into $2n$ cells, arranged as a $2$-row, $n$-column rectangle. To make painting easier, the canvas is wrapped around the side surface of a very low and wide cylinder, so the first column of the canvas is adjacent to the last column. If two cells on the canvas share a common edge, we say they are adjacent. That is, they are either in the same column, or in neighboring columns within the same row. Mathematically, we can represent each cell on the canvas by an ordered pair $(y,x)$, where $1\le y\le 2, 1\le x\le n$. Two cells $(y_1,x_1)$ and $(y_2,x_2)$ are adjacent if: - They are in the same row, i.e. $y_1=y_2$, and their columns are adjacent, i.e. $x_1+1\equiv x_2 \pmod n$ or $x_2+1\equiv x_1\pmod n$, or - They are in the same column, i.e. $x_1=x_2$. As soon as Bytie came to the canvas, he painted each of the $2n$ cells in a **different** color. For simplicity, we represent the colors by integers from $1$ to $2n$. Everyone who saw the child’s work was very surprised that such a small child could create such a grand piece. It even attracted the famous art critic Bytona Bitego. He decided to see for himself what fascinated people so much, and he will evaluate the painting using his own specially prepared method as follows: We choose a specific color interval $[l, r]$, and then we only consider the cells whose colors are within this interval. We define the curiosity value of this color interval as the number of connected components formed by these cells. If there exists a chain of adjacent cells whose colors are in $[l, r]$ that connects two cells with colors in $[l, r]$, then these two cells belong to the same component. Bytona Bitego wants to know, for each $v\in \{1,2,\ldots,k\}$, how many intervals have curiosity value equal to $v$. Your task is to answer his question.

The first line contains two integers $n,k$, representing the width of the canvas and the maximum curiosity value that Bajtona Bitego wants to know. The second line contains $n$ integers, giving the colors of the cells in the first row of the canvas. They are given from left to right, in increasing column order. Similarly, the third line contains $n$ integers, giving the colors of the cells in the second row of the canvas, in the same order as the first row. The numbers in the second and third lines together form a permutation of the integers from $1$ to $2n$.

Output one line with $k$ integers. The $v$-th integer is the number of intervals whose curiosity value is $v$.

For $100\%$ of the testdata, it holds that: $2\le n\le 10 ^ 5, 1\le k\le 10$。 Translated by ChatGPT 5