Mo, sqrt and search tricks

Questions 1 to 5 of 7

1. 1. Mo's algorithm uses the default block size B = n / sqrt(q). For n = 200000 positions and q = 200000 queries, what whole-number block size does the lesson's formula give, using integer division of the result?

   Type a number.

2. 2. An AI says Mo's algorithm runs in O(n + q) time, because each query only adds or removes a few values. What is wrong with that claim?

   Nothing, because the window moves once per query and each move is O(1).Each query moves the left pointer up to B steps, and the right pointer moves up to n steps per block. With B near sqrt(n), the total is about (n + q) * sqrt(n), not linear.The claim is right for sums, but wrong for counts, since counts need a Fenwick tree.Mo's algorithm needs O(n^2) time, so it cannot run within the limits at all.
3. 3. Which statements about Mo's algorithm are true?

   Pick every answer that is true.

   Alternating the direction of r from block to block lowers the right-pointer moves, compared with always sorting r in ascending order.The window must either undo a removal, or the solution must use a rollback variant that only adds values and then takes the temporary additions back out.Mo's algorithm handles point updates to the array with no change to the sort order.The default block size is n / sqrt(q).
4. 4. An AI proposes sqrt decomposition for range sums with point updates, with n = q = 200000. A Fenwick tree also handles this. Which choice is better, and why?

   Sqrt decomposition, because it is simpler to write than a Fenwick tree and the speed does not matter.A Fenwick tree, because sums combine cleanly in a tree node, so each update and query costs O(log n). Sqrt decomposition would cost about sqrt(n), which is about 447 steps per operation.Sqrt decomposition, because a Fenwick tree cannot store sums that change over time.Either one, because both cost O(n) per operation at this size.
5. 5. A persistent segment tree over the compressed values 0 to 3 (so m = 4 leaves) is built with three inserts, for the array [2, 0, 2]. Each insert copies the path from the root to one leaf, and that path has 3 nodes. How many new nodes are created in total?

   Type a number.