题目描述

对于长度为 $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,\ldots,n$，独立地回答如下问题：

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

输入格式

第一行包含一个整数 $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$。

输出格式

对于每个测试用例，输出一个二进制字符串 $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$。

样例

4
4 2
1 1 3 4
1 2
2 4
3 2
1 1 3
1 2
2 3
3 1
1 1 1
1 3
9 3
4 5 9 1 1 1 2 2 3
1 6
3 7
7 9

1011
101
111
100100001

样例说明

在第一个测试用例中：

• 对于 $x=1$，一种可行的重排列为 $a'=[1,1,3,4]$。
• 对于 $x=2$，不存在重排列 $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]$。

由 ChatGPT 5 翻译

来源

Codeforces 2162H，英文题名 Beautiful Problem。