P3560 [POI 2013] LAN-Colorful Chain

Little Bytie loves to play with colorful chains. Each chain consists of a certain number of colorful links. Bytie finds a contiguous fragment of a chain nice if it contains exactly $l_i$ links of color $c_i$ for every $i$ in $[1, m]$, and moreover contains no links of any other colors. The appeal of a chain is the number of its contiguous fragments that are nice. Given a sequence of length $n$ representing the colors of the chain and $m$ conditions (each condition gives a color $c_i$ and a required count $l_i$), count how many contiguous substrings are nice, that is: - For every $c_i$ among the $m$ conditions, the substring contains exactly $l_i$ occurrences of $c_i$. - For any color not listed among the $m$ conditions, the substring contains none of it.

- The first line contains two integers $n$ and $m$ ($1 \le m \le n \le 10^6$). These are the length of the chain and the number of conditions. - The second line contains $m$ integers $l_1, l_2, \dots, l_m$ ($1 \le l_i \le n$). - The third line contains $m$ integers $c_1, c_2, \dots, c_m$ ($1 \le c_i \le n$). These define that a nice fragment must contain exactly $l_i$ links of color $c_i$ for each $i$ and no links of any other colors. - The fourth line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), the colors of successive links of the chain.

Print a single integer, the number of nice contiguous fragments in the chain.

Constraints: For $100\%$ of the testdata, $1 \le m \le n \le 10^6$ and $1 \le a_i, l_i, c_i \le n$. Translated by ChatGPT 5