19439번 - Helter Skelter 다국어

A non-empty string $s$ is called a binary string if it consists only of characters '0' and '1'. A substring $s[l \ldots r]$ $(1 \le l \le r \le |s|)$ of string $s = s_{1} s_{2} \ldots s_{|s|}$ (where $|s|$ is the length of string $s$) is the string $s_{l} s_{l + 1} \ldots s_{r}$.

Professor Zhang has got a long binary string $s$ starting with '0', and he wants to know whether there is a substring of $s$ such that the number of occurrences of '0' and '1' in this substring are exactly $a$ and $b$, respectively, where $a$ and $b$ are two given integers.

Since the binary string is very long, we will compress it. The compression method is as follows:

• Split the string into runs of equal consecutive characters.
• Any two adjacent runs consist of different characters. Use the length of each run to represent the string.

For example, the runs of the binary string "00101100011110111101001111111" are $\{00, 1, 0, 11, 000, 1111, 0, 1111, 0, 1, 00, 1111111\}$, so it will be compressed into $\{2, 1, 1, 2, 3, 4, 1, 4, 1, 1, 2, 7\}$.

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n \le 1000$, $1 \le m \le 5 \cdot 10^5$): the number of runs and the number of queries. The next line contains $n$ integers: $x_1, x_2, \ldots, x_n$ ($1 \le x_i \le 10^6$) indicating the length of each run.

Each of the following $m$ lines contains two integers $a_i$ and $b_i$ ($0 \le a_i, b_i \le |s|$, $1 \le a_i + b_i \le |s|$) which means that Professor Zhang wants to know whether there is a substring of $s$ such that the number of occurrences of '0' and '1' in this substring are exactly $a_i$ and $b_i$, respectively.

There are no more than $200$ test cases, and the total size of the input is at most $20$ mebibytes. Additionally, the sum of $m$ in all test cases is at most $2 \cdot 10^{6}$.

For each test case, print a binary string of length $m$. The $i$-th digit must be '1' if the answer for the $i$-th query is "yes", or '0' otherwise.