CF1093G Multidimensional Queries

给定一个 $n$ 个点的数组 $a$，每个点位于 $k$ 维空间中。两点 $a_x$ 和 $a_y$ 之间的距离定义为 $ \sum\limits_{i=1}^{k} |a_{x,i} - a_{y,i}| $（即曼哈顿距离）。 你需要处理 $q$ 个如下两种类型的操作： - $1\ i\ b_1\ b_2\ \dots\ b_k$ —— 将第 $i$ 个点的坐标设为 $(b_1, b_2, \dots, b_k)$； - $2\ l\ r$ —— 查询区间 $[l, r]$ 内任意两点 $a_i$ 和 $a_j$ 之间的最大距离（$l \leq i, j \leq r$）。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 2 \times 10^5$，$1 \leq k \leq 5$），分别表示点的数量和空间的维度。 接下来 $n$ 行，每行包含 $k$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,k}$（$-10^6 \leq a_{i,j} \leq 10^6$），表示第 $i$ 个点的坐标。 接下来一行包含一个整数 $q$（$1 \leq q \leq 2 \times 10^5$），表示操作的数量。 接下来 $q$ 行，每行表示一个操作，格式如下： - $1\ i\ b_1\ b_2\ \dots\ b_k$（$1 \leq i \leq n$，$-10^6 \leq b_j \leq 10^6$）—— 将第 $i$ 个点的坐标设为 $(b_1, b_2, \dots, b_k)$； - $2\ l\ r$（$1 \leq l \leq r \leq n$）—— 查询区间 $[l, r]$ 内任意两点之间的最大距离。 保证至少有一个第二类操作。

对于每个第二类操作，输出一行答案。

由 ChatGPT 4.1 翻译