A × B (HARD)

Maintain whether each slot currently contains a value and, when it does, the value itself.

Use a segment tree whose node stores both the minimum and maximum value in its interval. An interval containing no value is represented by a separate empty state. When merging two nodes, return the nonempty node if exactly one side is empty. If both are nonempty, store the smaller minimum and the larger maximum.

A type 1 query changes one leaf to a present value. A type 3 query changes one leaf to the empty state. A type 2 query merges the nodes covering the requested interval. Print nothing if the result is empty; otherwise print the product of its minimum and maximum.

Since each value has absolute value at most $10^9$, the product can reach $10^{18}$, so a 64-bit integer type is required.

The time complexity per test case is $O((N+M)\log N)$, and the space complexity is $O(N)$.

Solution written by GPT5.6