座標圧縮とクエリ

配列 $A$ をそのまま保持し、クエリを順番に処理する。

種類 1 では、$A_l,\ldots,A_r$ を別の配列にコピーし、ソートして重複を取り除く。ソート済みの異なる値の列 $B$ における各 $A_i$ の lower_bound の位置が、圧縮後の値となる。区間外は変更しない。

種類 2 では、区間を走査して最小値 $m$ と最大値 $M$ を求める。浮動小数点数を使わず、各候補 $x$ について $|2x-(m+M)|$ を比較する。この値が最小となる候補のうち、最も小さい値を選ぶ。配列の値と中間計算には long long を使う。

種類 3 では、区間の各要素に $d$ を直接加える。

正当性: ソートして重複を除いた列における位置は、その値より小さい異なる値の個数と一致するため、種類 1 は正しい。種類 2 は区間に存在するすべての候補を調べ、目標値までの距離の $2$ 倍を正確に比較し、同距離の場合の規則も適用する。種類 3 は指定された要素だけを更新する。したがって、すべてのクエリは正しく処理される。

種類 1 の各クエリは $O(N\log N)$ 時間、それ以外はそれぞれ $O(N)$ 時間で処理できる。種類 1 は高々 $100$ 回なので、全体の時間計算量は $O(NQ+100N\log N)$、追加空間計算量は である。