Description

给定 $n$ 个 $k$ 维整点 $\{ a_i \}$,支持单点坐标修改,求区间 $[l,r]$ 内点对的最长曼哈顿距离。

Idea

$i,j$ 之间的曼哈顿距离被定义为 $\sum |a_{i,k}-a_{j,k}|$。我们可以把式子拆开,每一维上 $a_i$ 和 $a_j$ 取值的正负性一定是相反的。

考虑到 $k$ 比较小,我们可以枚举每个点的第 $i$ 维在距离计算公式中的正负性。

具体地,我们用集合 $S$ 表示一个点每个维度的正负性。用线段树维护区间内每种可能集合 $S$ 的最大值。也就是说,我们分别计算每个点对不同的集合 $S$ 的贡献。合法答案是所有互补集合对贡献和的最大值。

Code