P17396 [ICPC 2018 Shenyang R] The Kouga Ninja Scrolls

故事围绕着 $n$ 个互为对手的忍者氏族展开，氏族编号从 $1$ 到 $n$，同样也有 $n$ 名忍者，编号从 $1$ 到 $n$。对每一名忍者，其家族决定了他/她最初的信念与所属的氏族。但故事中会发生一些冲突，例如两个年轻的灵魂，面对各自家族的敌对却坠入爱河，可能会改变心意，一些忍者也可能叛逃至其他敌对的氏族。 这些忍者生活在一个相当宁静的小镇，镇上的小径简单明了，但他们却像一群野兽，时刻盯着其他氏族的忍者，不停逃亡并伺机杀戮。这片区域的领主知道，他们之间战争的终结取决于那些分属不同氏族且相距最远的忍者。 这正是作为领主忠实仆人的一只高贵秃鹫应当做的事情。现在你需要扮演这只秃鹫，实时向领主报告：在编号属于某个指定连续范围内的忍者中，分属不同氏族的两名忍者之间的最大距离是多少。具体而言，平面上两点之间的距离定义为曼哈顿距离，也就是它们笛卡尔坐标差的绝对值之和。

输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据的组数，最多为 $60$。 对于每组测试数据，第一行包含两个整数 $n$ 和 $m$，$n$ 表示氏族数量同时也是忍者的数量，$m$ 表示特殊的冲突与领主询问的总次数，满足 $1 \le n \le 10^5$，$1 \le m \le 10^5$。 接下来的 $n$ 行描述所有忍者的初始状态。其中第 $i$ 行包含三个整数 $x, y$ 和 $c$，表示第 $i$ 名忍者初始所在的位置为 $(x, y)$，初始所属的氏族为第 $c$ 个，满足 $-10^9 \le x, y \le 10^9$，$1 \le c \le n$。 再接下来的 $m$ 行按时间顺序描述了所有改变某人位置或氏族的特殊冲突，以及来自领主的所有询问。每行必须是以下三种形式之一： * $\text{1 k x y}$：第 $k$ 名忍者沿方向 $(x, y)$ 改变其位置；也就是说，他/她移动到新位置 $(x_0 + x, y_0 + y)$，其中 $(x_0, y_0)$ 是他/她原来的位置。 * $\text{2 k c}$：第 $k$ 名忍者改变心意，决定为第 $c$ 个氏族效力。 * $\text{3 l r}$：领主向其秃鹫询问，在编号从 $l$ 到 $r$（包含两端）的忍者中，分属不同氏族的两名忍者之间的最大距离。 上述 $m$ 行中出现的所有 $k, x, y, l, r$ 和 $c$ 均满足 $1 \le k, c \le n$，$-10^9 \le x, y \le 10^9$，$1 \le l \le r \le n$。 我们保证所有测试数据中 $n$ 的总和不超过 $5 \times 10^5$，$m$ 的总和也不超过 $5 \times 10^5$。

对于每组测试数据，首先输出一行包含 “Case #x:”（不含引号），其中 $x$ 是测试数据的编号，从 $1$ 开始。 然后，对于每个询问，在一行中输出一个整数作为答案。如果相关的所有忍者都属于同一氏族，则输出 $0$。

《甲贺忍法帖》（The Kouga Ninja Scrolls）是一部关于忍者的历史奇幻小说，由日本作家山田风太郎于 1958 年至 1959 年间创作。这是山田在 1958 年至 2001 年间创作的《忍法帖》系列的第一卷。该书由 Geoff Sant 翻译为英文，并于 2006 年 12 月由 Del Rey 出版。 ——摘自维基百科，自由的百科全书 翻译由 DeepSeek V4 Pro 完成