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))) < 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 $ ?

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.

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

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] $ .