DMOPC '18 Contest 1 P5 - Sorting

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 1.0s
Java 2.5s
Python 2.5s
Memory limit: 256M

Author:
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.

Constraints

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
Q = 1

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, \dots, 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

2
2

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

0
1
2

Comments

There are no comments at the moment.