Coordinate Compression and Queries

Maintain the array $A$ explicitly and process the queries in order.

For a type 1 query, copy $A_l,\ldots,A_r$, sort the copy, and remove duplicates. The lower_bound index of each original value in this sorted list is its compressed coordinate. Do not change elements outside the selected range.

For a type 2 query, scan the range to obtain its minimum $m$ and maximum $M$. Instead of using floating-point arithmetic, compare $|2x-(m+M)|$ for every candidate value $x$. Choose the smallest value among those minimizing this expression. Store array values and intermediate calculations in .

For a type 3 query, add $d$ directly to every element in the selected range.

Correctness: The position in the sorted distinct-value list equals the number of distinct smaller values, so type 1 is correct. Type 2 considers every value occurring in the range, compares precisely twice its distance to the required midpoint, and applies the tie rule. Type 3 changes exactly the required elements. Therefore all queries are processed correctly.

Each type 1 query takes $O(N\log N)$ time, while each other query takes $O(N)$ time. There are at most $100$ type 1 queries, giving total time $O(NQ+100N\log N)$ and auxiliary space .