AT_maximum_2013_h さいたまの矛盾

SAITAMA 组织是一个由 $n$ 名成员组成的秘密组织，每个成员都有一个唯一编号：1, 2, ..., n。他们日以继夜地训练，目标是消灭敌对组织 GUNMA。他们对内部的实力排名非常在意，经常会进行类似「我比他强」「我是 B 级第一，比50号以后的人都强」「他是我们中最弱的」这样的对话。 组织内部的任意两个人之间都有实力关系，对于成员 $a$ 和 $b$，要么 $a$ 比 $b$ 强，要么 $b$ 比 $a$ 强。这种关系满足传递性和非自反性：如果 $a$ 比 $b$ 强，且 $b$ 比 $c$ 强，则 $a$ 肯定比 $c$ 强。同时，没有人会比自己强（弱关系也是同样的道理）。 A 先生作为 GUNMA 的间谍，监听了这些谈话，他察觉到其中可能有矛盾。然而由于 SAITAMA 组织成员众多，他无法确定是哪句话引发了矛盾，甚至怀疑自己是不是感知错误。 幸运的是，A 先生记住了所有成员的每句话及其顺序。奇怪的是，他发现所有的发言都是以「编号为 $p$ 的成员比编号在 $l$ 到 $r$ 之间的所有人都强／弱」这种模式出现的。 A 先生想要找出首次出现矛盾的发言。他希望查明一个整数 $k$，使得第 1 条到第 $k-1$ 条发言中没有矛盾，而第 1 条到第 $k$ 条中出现了矛盾。你的任务是帮助 A 先生找到第一个导致矛盾的发言编号。 ### 输入格式 输入如下格式： > $n\ m\ p_1\ c_1\ l_1\ r_1\ p_2\ c_2\ l_2\ r_2\ \ldots\ p_m\ c_m\ l_m\ r_m$ 1. 第一行由两个整数 $n$ 和 $m$ 组成，用空格分隔。 - $n$ 表示成员的数量，$1 \leq n \leq 1,000,000,000$。 - $m$ 表示发言的数量，$1 \leq m \leq 1,000$。 2. 接下来的 $m$ 行，每行包含发言信息，包括整数 $p_i$、字符 $c_i$、整数 $l_i$ 和整数 $r_i$，由空格分隔。 - 如果 $c_i$ 是 `s`，表示「编号为 $p_i$ 的成员，比编号在 $l_i$ 到 $r_i$ 之间的所有成员都强」。 - 如果 $c_i$ 是 `w`，表示「编号为 $p_i$ 的成员，比编号在 $l_i$ 到 $r_i$ 之间的所有成员都弱」。 - $p_i$ 满足 $1 \leq p_i \leq n$，$l_i$ 和 $r_i$ 满足 $1 \leq l_i \leq r_i \leq n$。 ### 输出格式 输出第一个矛盾的发言编号。如果没有任何矛盾，输出 `0`。输出应为标准输出，并在末尾换行。 ### 数据范围与提示 - 成员数 $n$ 有可能达到 10 亿，而发言总数 $m$ 最高为 1000，所以请注意程序的优化。 - 每条发言的编号和范围都合法。 ### 示例 **输入** ``` 4 5 4 w 1 3 3 w 2 2 2 s 3 4 3 s 1 1 1 s 2 2 ``` **输出** ``` 5 ``` **说明** - 前四条发言一致，但第五条发言与之前的信息矛盾。 - 根据前四条发言判断，成员2比成员3强，成员3比成员1强，推理得出成员2比成员1强。 - 但是第五条发言表示成员1比成员2强，产生矛盾。 **输入** ``` 2 4 1 w 2 2 1 s 2 2 2 w 1 1 2 s 1 1 ``` **输出** ``` 2 ``` **说明** - 对于编号1，要么比编号2强，要么比编号2弱，但不能两者兼备。第二条发言与第一条矛盾。 - 虽然后续发言也有矛盾，但以最早的矛盾编号 `2` 作为结果。 **输入** ``` 1000000000 4 1 w 5 100000 1000000 s 100 888888 1000 w 10000 10000 1000000000 s 1 999999999 ``` **输出** ``` 0 ``` **说明** - 没有矛盾。每一个成员间的关系完全符合发言所描述的��辑。 **本翻译由 AI 自动生成**

无

无