DMOPC '18 Contest 1 P5 - Sorting

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Java 5.0s
Python 5.0s
Memory limit: 256M

Problem type

You are considering a permutation P of 0 to N-1 and a non-negative integer C. The elements at indices i and j may be swapped only if P_i \oplus P_j \le C where A\oplus B denotes the XOR of A and B. However, C has not yet been decided. What is the smallest possible non-negative integer C so that this permutation may be sorted from least to greatest?

To make this more interesting, the permutation will be updated. You are given Q updates of the form u v meaning that P_u and P_v have been swapped. After each of the Q updates, what is the best C?

Note that the indices are 1-indexed, but the values are from 0 to N-1.


For all 1\le i\le N,\ 0\le P_i\le N-1.
P is a permutation, so each element from 0 to N-1 will appear exactly once.
1\le u, v\le N

Subtask 1 [20%]

1\le N\le 400
1\le Q\le 400

Subtask 2 [30%]

1\le N\le 200\ 000

Subtask 3 [30%]

1\le N\le 50\ 000
1\le Q\le 50\ 000

Subtask 4 [20%]

1\le N\le 200\ 000
1\le Q\le 200\ 000

Input Specification

The first line will contain two space-separated integers, N and Q. The next line will contain N space-separated integers, P_1, P_2, \ldots, P_N.
The following Q lines will each contain two space-separated integers, u and v, the indices to be swapped.

Output Specification

For each query, output a line containing a single non-negative integer, the smallest possible C given the current permutation.

Sample Input 1

4 2
2 3 1 0
4 3
1 1

Sample Output 1


Explanation for Sample 1

After the first update, the permutation is 2, 3, 0, 1. Swap 2 and 0, then 3 and 1.
The second update doesn't change anything.

Sample Input 2

4 3
1 0 2 3
1 2
3 4
1 4

Sample Output 2



There are no comments at the moment.