Editorial for DMOPC '18 Contest 5 P6 - An XOR Problem
Submitting an official solution before solving the problem yourself is a bannable offence.
For the first subtask, a few initial observations are needed. Note that if for some and , then nodes and may be connected at no cost, even after updates. So multiple nodes with the same value may be discarded and there will be at most important nodes. Another observation is that there are only residues modulo , so we can precompute the answer for each of these residues and then answer each update in . With these in mind, a straightforward implementation of Kruskal's can pass in time.
For the next subtask, the Kruskal's must be optimized to subquadratic time. Split the nodes into two sets: those with the largest bit, and those without. Note that because the edges are sorted by weight, the edges between nodes in the same set will always be considered before the edges between the two sets. To combine the two sets, only one edge is necessary (since each set is already connected) and this edge can be found by building a trie from one set and checking every node in the other set against the trie.
Note that the Kruskal's in the solution to the second subtask implicitly formed a binary tree. For the third subtask, we will focus on this structure. Consider the subtrees with height from the bottom of the complete binary tree. Note that if divides , then for , these subtrees will move but they themselves will not change. Then we can precompute the total weight within each of these subtrees, as well as the minimum weight between every two of these subtrees. Then for each update, we only need to apply the Kruskal's to the first levels and use the precomputed values. Finally, since divides , there are only important residues mod .
For the final subtask, we build on this idea of unchanging subtrees of height . To force this condition in subtask 3, we can construct a sequence of 's which has most 's divisible by . For example, when , one such sequence of 's would be which covers all residues mod . However, even after constructing this sequence, we cannot simply apply the exact same idea as subtask 3. This is because we need to do the precomputing between every pair of subtrees for each time is not divisible by , which is times. This would lead to a time complexity of for precomputing alone.
To deal with this, an optimization is necessary for the precomputing. Consider subtrees of height in these subtrees of height . There are only possible subtrees. The minimum edge weight between every two of these subtrees can be precomputed and this only needs to be done once. Then, these values are used in precomputing the values of subtrees of height , and then the solution from subtask 3 can be used.
In the model solution, we choose .