モラトリアムライフ

自由を求めて

精進記録 : Educational Codeforces Round #56 G - Multidimensional Queries

問題概要

n 個の k 次元上の点 a_1, a_2, ..., a_n \in \mathbb{Z}^{k} が与えられる.
このとき, q 個の次のクエリに答えよ.
　　　1. i \in \mathbb{N}, b \in \mathbb{Z}^{k} が与えられる. a_i を b に変更する.
　　　2. l, r \in \mathbb{N} \, \, (\, l \leq r\, ) が与えられる. マンハッタン距離1の最大値 \displaystyle{\max_{ l \leq i, j \leq r} \, || a_i - a_j ||_{1}} を出力する.

制約

  • 1 \leq n \leq 2 \cdot 10^{5}
  • 1 \leq k \leq5
  • 1 \leq q \leq 2 \cdot 10^{5}
  • 1 \leq l \leq r \leq n
  • -10^{6} \leq a_{i, \, j} , b_{i, \, j} \leq 10^{6} (1 \leq i \leq n , 1 \leq j \leq k)

問題リンク codeforces.com

考察

愚直に考えると、変更は O(k) , 最大値を求めるのに全てのペアに調べると O(k n^{2}) がかかってしまい, 到底間に合わない(特に, 最大値を求める部分). そこで k が 5以下という非常に小さい制約があることから, おそらくこれを利用して, 最大値を求める部分を高速に処理できればよいだろうと考えられる(今持っている情報を k に載せたい).

さて, ここでマンハッタン距離について一度考えることにしよう.

\displaystyle{ || x - y ||_{1} = \sum_{i = 1}^{k} |x_{i} - y_{i}| }

マンハッタン距離は絶対値が含まれているため、一つの点を固定したときに、その固定した点の各成分が正として振る舞うのか, それとも負として振る舞うのかはもう一点との関係によって定まってくる. それゆえ距離の最大値を求める際に, 各点の情報が2次元的に必要になるように感じられる.

しかし, もし絶対値がなければどうだろうか. 2点間の成分の和の最大値というのは, 各点の成分の和の最大値と最小値が分かれば容易に求めることができる(ある種1次元的な情報に落とし込める). そして, これは点更新セグメント木を使って更新, クエリともに O(\log n) で高速に処理することができる.

\begin{aligned} \max_{x, y \in S} \sum_{i=1}^{k} (x_{i} - y_{i} ) &= \max_{x \in S} \sum_{i = 1}^{k} x_{i} + \max_{y \in S} \left (-\sum_{i = 1}^{k} y_{i} \right) \\ &= \max_{x \in S} \sum_{i = 1}^{k} x_{i} - \min_{y \in S} \sum_{i = 1}^{k} y_{i} \end{aligned}


元の問題に視点を戻すと, 求めるられているのは絶対値の和である. どのようにして求めることができるだろうか. それは 各成分を正負の方向に移動させた空間上で、上の値を求めることである. なぜなら 一般に実数 a に対して a \leq |a| かつ -a \leq |a| であるので, 任意の数列 a_1, a_2, ... に対して, 少し雑な記法を許すと \sum_{i} \pm a_{i} \leq \sum_{i} |a_{i} | が成り立つからである. 2

正負の方向を bit列で管理して (これは高々 2^{5} = 32 個) 最大値と最小値の差を求めるセグメント木を使って全方向を探索すれば、このクエリに O(2^{k} \cdot \log n) で答えることができ、更新も O(2^{k} \cdot (k + \log n)) で十分高速に行うことができる. これにより、この問題を解くことができた

実装例

codeforces.com

  1. マンハッタン距離とは L1 ノルムのこと. a \in \mathbb{R}^{k} に対して || a ||_{1} = \sum_{j = 1}^{k} |a|. 各成分の絶対値の和↩

  2. より正確には, 「上記によって下から抑える. また a = |a| \land -a = |a| が成り立つので 等号を与えるような各成分への正負の方向が存在する」のでこれを全探索することにより求められる.↩