CF1214G Feeling Good

最近，生物学家们得出了一个关于如何判断变色龙心情的有趣结论。我们可以将变色龙的身体看作一个 $n \times m$ 的矩形表格，每个格子可以是绿色或蓝色，并且可以在这两种颜色之间切换。我们用 $(x, y)$（$1 \leq x \leq n$，$1 \leq y \leq m$）表示第 $x$ 行第 $y$ 列的格子。 我们定义变色龙的“好心情证明”为：存在四个格子，它们是某个子矩形的四个角，并且这四个格子中，对角线上的格子颜色相同，但四个格子的颜色不全相同。形式化地说，就是存在四个格子 $(x_1, y_1)$、$(x_1, y_2)$、$(x_2, y_1)$、$(x_2, y_2)$，其中 $1 \leq x_1 < x_2 \leq n$，$1 \leq y_1 < y_2 \leq m$，满足 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的颜色相同，$(x_1, y_2)$ 和 $(x_2, y_1)$ 的颜色相同，但这四个格子的颜色不全一样。研究发现，只要存在这样的四个格子，变色龙就是好心情；反之，如果不存在这样的四个格子，变色龙就是坏心情。 你的任务是帮助科学家编写一个程序，在每次颜色变化后判断变色龙的心情。如果变色龙是好心情，还需要输出任意一组满足条件的四个数 $x_1$、$y_1$、$x_2$、$y_2$，使得 $(x_1, y_1)$、$(x_1, y_2)$、$(x_2, y_1)$、$(x_2, y_2)$ 构成好心情证明。 初始时，变色龙身体的所有格子都是绿色。之后，变色龙的颜色会发生若干次变化。每次变化会将某一行的一个连续区间的颜色全部反转。具体来说，每次变化由三个整数 $a$、$l$、$r$（$1 \leq a \leq n$，$1 \leq l \leq r \leq m$）描述，将第 $a$ 行第 $l$ 列到第 $r$ 列之间的所有格子的颜色反转。 请你在每次变化后，输出变色龙的心情。如果是好心情，还要输出一组好心情证明。

第一行包含三个整数 $n$、$m$、$q$（$1 \leq n, m \leq 2000$，$1 \leq q \leq 500\,000$），分别表示表格的大小和颜色变化的次数。 接下来的 $q$ 行，每行包含三个整数 $a_i$、$l_i$、$r_i$（$1 \leq a_i \leq n$，$1 \leq l_i \leq r_i \leq m$），表示第 $i$ 次颜色变化。

输出 $q$ 行。第 $i$ 行表示前 $i$ 次颜色变化后变色龙的心情。 如果变色龙是坏心情，输出唯一的整数 $-1$。 否则，输出四个整数 $x_1$、$y_1$、$x_2$、$y_2$（$1 \leq x_1 < x_2 \leq n$，$1 \leq y_1 < y_2 \leq m$），使得 $(x_1, y_1)$、$(x_1, y_2)$、$(x_2, y_1)$、$(x_2, y_2)$ 构成好心情证明。如果有多组答案，输出任意一组均可。

由 ChatGPT 4.1 翻译