CF2162H.Beautiful Problem

For an array $a$ of length $n$ and three integers $x$, $l$, and $r$（$1 \le l \le r \le n$), define:

f(a,x,l,r) = \\begin{cases} 0, & \\text{if} & (x-\\min\_{j=l}^{r}(a\_j)) \\cdot (x-\\max\_{j=l}^{r}(a\_j))) \\lt 0 \\\\ 1, & \\text{if} & (x-\\min\_{j=l}^{r}(a\_j)) \\cdot (x-\\max\_{j=l}^{r}(a\_j))) \\ge 0 \\end{cases}

You are given an array $a$ of length $n$ ($1 \le a_i \le n$), and $m$ intervals $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$).

For each $x=1, 2, \dots, n$, answer the following question independently:

• Does there exist a rearrangement $a'$ of $a$, such that for all $1 \le i \le m$, $f(a',x,l_i,r_i) = 1$?

对于长度为 $n$ 的数组 $a$ 和三个整数 $x$、$l$ 与 $r$（满足 $1 \le l \le r \le n$），定义：

$$f(a,x,l,r) = \begin{cases} 0, & \text{若} & (x-\min_{j=l}^{r}(a_j)) \cdot (x-\max_{j=l}^{r}(a_j)) < 0 \\ 1, & \text{若} & (x-\min_{j=l}^{r}(a_j)) \cdot (x-\max_{j=l}^{r}(a_j)) \ge 0 \end{cases}$$

给定一个长度为 $n$ 的数组 $a$（满足 $1 \le a_i \le n$）以及 $m$ 个区间 $[l_i, r_i]$（满足 $1 \le l_i \le r_i \le n$）。

对每个 $x = 1, 2, \dots, n$，独立回答以下问题：

• 是否存在 $a$ 的一个重排 $a'$，使得对所有 $1 \le i \le m$，均有 $f(a',x,l_i,r_i) = 1$？

The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Description of each testcase follows.

The first line contains two integers $n$ and $m$ ($2 \le n \le 2000$, $1 \le m \le 2000$).

The next line contains $n$ space-separated integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$).

The next $m$ lines each contain two space-separated integers $l_i, r_i$ ($1 \le l_i \le r_i \le n$), each denoting an interval.

It is guaranteed that the sum of $n^2$ and the sum of $m^2$ over all test cases does not exceed $4 \cdot 10^6$, respectively.

第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试用例的数量。每个测试用例的描述如下：

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2000$，$1 \le m \le 2000$）。

第二行包含 $n$ 个以空格分隔的整数 $a_1, a_2, \cdots, a_n$（$1 \le a_i \le n$）。

接下来的 $m$ 行，每行包含两个以空格分隔的整数 $l_i, r_i$（$1 \le l_i \le r_i \le n$），分别表示一个区间。

保证所有测试用例中 $n^2$ 的总和与 $m^2$ 的总和均不超过 $4 \cdot 10^6$。

For each test case, output a binary string $s$. For $x=1,2,\ldots,n$, $s_x=1$ only if there exists a rearrangement $a'$ of $a$, such that for all $1 \le i \le m$, $f(a',x,l_i,r_i) = 1$. Otherwise, $s_x=0$.

对于每个测试用例，输出一个二进制字符串 $s$。对 $x=1,2,\ldots,n$，当且仅当存在数组 $a$ 的一个重排 $a'$，使得对所有 $1 \le i \le m$ 均满足 $f(a',x,l_i,r_i) = 1$ 时，$s_x=1$；否则 $s_x=0$。

In the first test case,

• For $x=1$, one valid rearrangement is $a'=[1,1,3,4]$.
• For $x=2$, there is no rearrangement $a'$ of $a$ satisfying $f(a',2,1,2)=f(a',2,2,4)=1$.
• For $x=3$, the only valid rearrangement is $a'=[4,3,1,1]$.
• For $x=4$, one valid rearrangement is $a'=[1,1,3,4]$.

在第一个测试用例中：

• 对于 $x=1$，一个合法的重排是 $a'=[1,1,3,4]$。
• 对于 $x=2$，不存在数组 $a$ 的重排 $a'$ 满足 $f(a',2,1,2)=f(a',2,2,4)=1$。
• 对于 $x=3$，唯一合法的重排是 $a'=[4,3,1,1]$。
• 对于 $x=4$，一个合法的重排是 $a'=[1,1,3,4]$。