DMOPC '18 Contest 5 P6 - An XOR Problem

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.5s
Memory limit: 256M

Problem type

A graph has N nodes labelled from 1 to N where node i is assigned a K-bit integer x_i. Every pair of nodes (i, j) has an edge between them with weight x_i \oplus x_j where \oplus denotes the XOR operation. You want to know the total weight of this graph's minimum spanning tree. However, the values assigned to each node sometimes change. In particular, you will receive Q updates of the form c. For each update, x_i is changed to (x_i+c) \bmod 2^K for every i=1, 2, \dots, N. After each update, output the weight of the minimum spanning tree.


For all subtasks:

0 \le x_i, c \le 2^K-1

1 \le N, Q \le 20\,000

Subtask 1 [20%]

1 \le K \le 7

Subtask 2 [20%]

1 \le K \le 14

1 \le Q \le 20

Subtask 3 [20%]

6 \le K \le 14

c is divisible by 2^5 for every update.

Subtask 4 [40%]

1 \le K \le 14

Input Specification

The first line will contain two space-separated integers, N and K.
The second line will contain N space-separated integers, x_1, x_2, \dots, x_N.
The third line will contain a single integer, Q.
The next Q lines will each contain a single integer, c.

Output Specification

Output the weight of the minimum spanning tree after each of the Q updates.

Sample Input

3 2
1 2 3

Sample Output


Explanation for Sample

After the first update, the x values are 0, 2, 3. Then the minimum total weight is (0 \oplus 2) + (2 \oplus 3) = 3. After the second update, the x values are 0, 1, 3. The minimum total weight is (0 \oplus 1) + (1 \oplus 3) = 3.


There are no comments at the moment.