2247D1.md (3469B)
1 Source: https://codeforces.com/problemset/problem/2247/D1 2 3 D1. XOR Sorting (Easy Version) 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 This is the easy version of the problem. The only difference between the versions is that in this version, $q = 0$. 22 23 Note that zero-based indexing is used in this problem. 24 25 For an array $b$ consisting of $m$ positive integers, define $f(b)$ as follows. 26 27 For a non-negative integer $k$, we say that $b$ can be $k$-sorted if it can be sorted in non-decreasing order by performing the following operation any number of times: 28 29 1. Choose two indices $i$ and $j$ ($0 \le i \lt j \le m - 1$) such that $i \oplus j \le k$$^{\text{∗}}$. Note that the condition applies to the indices $i$ and $j$, not to the elements $b_i$ and $b_j$. 30 2. Swap the elements $b_i$ and $b_j$. 31 32 The value $f(b)$ is defined as the smallest non-negative integer $k$ such that the array $b$ can be $k$-sorted. 33 34 You are given an array $a$ of length $n$, consisting of positive integers. You will perform $q$ updates on $a$. Each update has the following form: 35 36 * $i \; x$: assign $a_i = x$. 37 38 Note that the updates are persistent. In other words, each update affects all subsequent states of the array. 39 40 For each of the $q + 1$ states of $a$ — the initial state and the state after each of the $q$ updates — find the value of $f(a)$. 41 42 $^{\text{∗}}$$\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) 43 44 Input 45 46 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 47 48 The first line of each test case contains two integers $n$ and $q$ ($1 \le n \le 10^6, q = 0$) — the length of the array $a$ and the number of updates. 49 50 The second line of each test case contains $n$ integers $a_0, a_1, \ldots, a_{n - 1}$ ($1 \le a_i \le 10^9$) — the array $a$. 51 52 The $j$-th of the following $q$ lines contains two integers $i_j$ and $x_j$ ($0 \le i_j \lt n$, $1 \le x_j \le 10^9$) — the description of the $j$-th update. This update means that the assignment $a_{i_j} = x_j$ is performed. 53 54 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$. 55 56 It is guaranteed that the sum of $q$ over all test cases does not exceed $10^6$. 57 58 Output 59 60 For each test case, output $q + 1$ integers — the values of $f(a)$ for the initial state of the array and after each of the $q$ updates, in order. 61 62 Example 63 64 Input 65 66 ``` 67 3 68 69 3 0 70 71 2 3 4 72 73 2 0 74 75 1000000000 999999999 76 77 6 0 78 79 2 5 3 4 1 6 80 ``` 81 82 Output 83 84 ``` 85 0 86 87 1 88 89 4 90 ``` 91 92 Note 93 94 In the first example, the array is $a = [2, 3, 4]$. It is already sorted, so $f(a) = 0$. 95 96 In the second example, the array is $a = [10^9, 10^9 - 1]$. We can swap $a_0$ and $a_1$, transforming $a$ as follows: $[\color{red}{10^9}, \color{red}{10^9 - 1}] \rightarrow [\color{red}{10^9 - 1}, \color{red}{10^9}]$. Therefore, $f(a) = 0 \oplus 1 = 1$. 97 98 In the third example, the array is $a = [2, 5, 3, 4, 1, 6]$. We can perform swaps using the index pairs $(0, 1)$ and $(0, 4)$, transforming $a$ as follows: $[\color{red}{2}, \color{red}{5}, 3, 4, 1, 6] \rightarrow [\color{red}{5}, \color{red}{2}, 3, 4, 1, 6]$, $[\color{red}{5}, 2, 3, 4, \color{red}{1}, 6] \rightarrow [\color{red}{1}, 2, 3, 4, \color{red}{5}, 6]$. It can be shown that no smaller value of $k$ is sufficient, so $f(a) = \max(0 \oplus 1, 0 \oplus 4) = 4$.