← 返回题目列表

Codeforces · 2162/H

H. 美丽的问题

中文机器翻译题面 查看原题

对于长度为 $$$n$$$ 的数组 $$$a$$$ 和三个整数 $$$x$$$、$$$l$$$ 和 $$$r$$$($$$1 \le l \le r \le n$$$),定义:

$$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}$$

给定一个数组 $$$a$$$,长度为 $$$n$$$ ($$$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$$$?

输入

第一行包含一个整数 $$$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$$$, $$$s_x=1$$$ 仅当存在 $$$a$$$ 的重新排列 $$$a'$$$ 时,这样对于 全部 $$$1 \le i \le m$$$,$$$f(a',x,l_i,r_i) = 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$$$ 的重新排列 $$$a'$$$。
  • 对于 $$$x=3$$$, 仅 仅有的 有效的重新排列为 $$$a'=[4,3,1,1]$$$。
  • 对于 $$$x=4$$$,一个有效的重新排列是 $$$a'=[1,1,3,4]$$$。