Editorial for Riolku's Mock CCC S5 - Keen Keener Multiset

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Plasmatic

Subtask 1

This subtask was intended to reward brute force solutions.

Time Complexity: $\mathcal{O}(NQ)$ ~\mathcal{O}(NQ)~

Subtask 2

Maintaining a dynamic prefix-XOR array suffices.

Time Complexity: $\mathcal{O}((N+Q) \log a_i)$ ~\mathcal{O}((N+Q) \log a_i)~

Subtask 3

A trie can be augmented to support range XOR queries. To deal with type $2$ ~2~ operations, use a lazy value. If the current bit is $1$ ~1~, swap the children of the node. This solution can be adapted to remove the laziness entirely.

Time Complexity: $\mathcal{O}((N+Q) \log a_i)$ ~\mathcal{O}((N+Q) \log a_i)~

Subtask 4

Here we present a SQRT decomposition solution on the values. Let $b$ ~b~ be the block size where $b=2^k$ ~b=2^k~ where $k \le 0$ ~k \le 0~.

We'll focus on type $2$ ~2~ operations as type $1$ ~1~ and $3$ ~3~ operations are quite simple and only require maintaining a cumulative XOR value in each block along with a frequency array.

As the block size is a power of $2$ ~2~, we can consider the top and bottom bits independently, which means that type $2$ ~2~ operations only require moving around blocks and changing a flag which denotes the cumulative XOR value of the bottom bits in the block (and brute forcing the update in partially covered blocks). The problem now is when two blocks are moved to the same position, we have to merge them as having multiple blocks that occupy the same range of values can result in quadratic time complexity.

However, we can show that the total number of merges is $\mathcal{O}(2^{18-k}+Q)$ ~\mathcal{O}(2^{18-k}+Q)~ if we do not merge two blocks when one of them is empty, meaning that we can brute force the merges. Consider the following:

Initially, there will be at most $2^{18-k}$ ~2^{18-k}~ blocks with values
Each type $1$ ~1~ query can create at most $1$ ~1~ non-empty block
Each type $2$ ~2~ query can create at most $2$ ~2~ non-empty blocks. The proof is the following:
- Non-empty blocks can only be created from values in partially covered blocks where the update is brute forced
- Obviously, the number of partially covered blocks is at most $2$ ~2~
- As the block size is a power of $2$ ~2~, the top $2^{18-k}$ ~2^{18-k}~ bits of the values that are XORed in each partially covered block will all be the same after being XORed. This means that they will all fall into the same new block
Each merge removes one non-empty block

Time Complexity: $\mathcal{O}(N+Q\sqrt{a_i})$ ~\mathcal{O}(N+Q\sqrt{a_i})~

Comments

13
ecnerwal commented on Feb. 16, 2021, 6:05 a.m. ← edited →
There's a simple $\mathcal{O}((N+Q) \log a_i)$ ~\mathcal{O}((N+Q) \log a_i)~ solution for subtask 4; it's essentially the same as the SQRT solution given, but stores trie nodes with lazy xor updates, and then merges trie nodes instead of blocks. In particular, to do operation 2:

Split the trie into 2 tries, one of which contains all $l \le a_i \le r$ ~l \le a_i \le r~ and the other containing all other values.

Apply a lazy xor update to the first trie.

Merge the two tries recursively back into one (propagating as necessary).

The split step will create at most $\mathcal{O}(\log a_i)$ ~\mathcal{O}(\log a_i)~ new nodes, and each nontrivial step of the merge will delete one trie node, so the total runtime amortizes to $\mathcal{O}((N+Q) \log a_i)$ ~\mathcal{O}((N+Q) \log a_i)~.

11

Riolku commented on Feb. 16, 2021, 6:10 a.m.

We considered this pre-contest, but couldn't prove the runtime as easily. That said, this solution is very clean, and I love the split-merge lazy trie approach, so thanks for your comment.

Note: DMOJ uses ~, not $, for math, and you can use \mathcal for nice time complexities.