CodeForces Round #431 (Div.2) E - Goodbye Souvenir についての記事です．
問題へのリンク
https://codeforces.com/contest/849/problem/E
経緯
Yoika さんが主催している Morningforces というバーチャルコンテスト で出て，解けませんでした． 公式解説 を読んだのですが，最後に出てくる座標圧縮云々がよく分かりませんでした．
問題概要
整数列 $a = a_1, \ldots, a_k $ に対して，$m(a)$ を，$a$ に現れる各数 $x$ に対して，$x$ が最後に現れる位置と最初に現れる位置との差の総和として定義する．例えば，$m(1, 2, 3, 1, 3, 2, 1) = (7-1) + (6-2) + (5- 3) = 12$．最初に長さ n の整数列 a が与えられる．各要素は1以上n以下．次の2種類のクエリ (全部で$m$個) を処理せよ．$ 1 \leq n, m \leq 100,000$．
- p, x が与えられて，aのp番目の要素をxに書き換える．
- l, r が与えられて，$ m(a[l:r]) $ を求める．
解法
ということで，実装手段を除いては公式解説をなぞっています．
$x$ が出てくる位置を $p_1, \ldots, p_k$ と書くと，$x$ による寄与は $ (p_2 - p_1) + \cdots + ( p_k - p_{ k - 1 } ) $ である． ある数が位置 s に現れ，次には位置 t に現れるという状況の時，2次元平面内の 点 $(t, s)$ に値 $ t - s $ を割り振ることにする． すると，位置 p から q までの a の部分列での値は，2次元平面内の長方形 $ [ p, q + 1) \times [p, n + 1) $ に割り振られた値の総和に等しい．
つまり，長方形 $ [1, n + 1) \times [1, n + 1) $ に対して，以下の操作が高速に行えれば良い．
- 1点に値を割り振る．
- 部分長方形に割り振られた値の総和を求める．
セグメント木と同じ考え方でできる． 通常のセグメント木は1次元で区間を2分割していくが， 2次元になっても，長方形を4分割することにすれば原理は同じ． ただし，最初に全部のセルを作ろうとすると $ \Omega ( n^2 )$ 必要なので間に合わない． そこで，ノードは必要になったときだけ生成する． 下のコードを見れば， 普通のセグメント木と同じように書けることが分かると思う． どちらのクエリも $O(\log n)$ で処理できるので， 全体で計算量は $ O(m\log n) $ となる．