← 返回题目列表

Codeforces · 1641/C

C. 匿名很重要

中文机器翻译题面 查看原题

在医生的工作中,保持客户和检查结果的匿名性非常重要。测试结果通过电子邮件亲自发送给每个人,但人们非常不耐烦,他们想立即知道结果。

这就是为什么在“De-vitro”测试实验室中,医生想出了一种实验方法来报告结果。我们假设 $$$n$$$ 人按照队列的顺序参加了测试。然后,主治医生 Sam 可以针对某些值 $$$l$$$ 和 $$$r$$$ 做出多个语句,在每个语句中告知从 $$$l$$$-th 到 $$$r$$$-th(含)的队列中的人员中是否有病人。

在这个过程中,Sam会检查这个计划的效果如何,并且会感兴趣是否有可能从他公布的信息中找出第$$$i$$$人的测试结果。如果能做到的话,那么那个病人到底有病还是没病。

帮助 Sam 测试他的计划。

输入

第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — 人数和查询数。

在接下来的 $$$q$$$ 行中,给出了查询的描述。该行中的第一个数字是 $$$t$$$($$$t = 0$$$ 或 $$$t = 1$$$) — 查询的类型。

如果 $$$t = 0$$$,则该行还包含三个整数 $$$l、r、x$$$($$$1 \le l \le r \le n$$$、$$$x = 0$$$ 或 $$$x = 1$$$)。这个查询意味着 Sam 告诉队列中从第 $$$l$$$ 到第 $$$r$$$(含)的人中:

- 至少有一名病人,如果 $$$x=1$$$,
- 如果$$$x=0$$$,则没有病人。

如果 $$$t = 1$$$,则该行还包含一个整数 $$$j$$$ ($$$1 \le j \le n$$$) — 患者在队列中的位置,Sam 想知道其状态。

所有查询都是正确的,这意味着始终存在长度为 $$$n$$$ 的队列示例,其中所有报告的结果(来自 $$$t = 0$$$ 的查询的语句)均为 true。

输出

在每个 Sam 问题($$$t = 1$$$ 查询)之后打印:

- “NO”,如果病人肯定没有生病,
- “是”,如果患者确实生病了。
- “N/A”,如果无法明确识别具有给定信息的患者的状态。

示例

输入 #1

6 9
0 4 5 0
1 5
1 6
0 4 6 1
1 6
0 2 5 1
0 2 2 0
1 3
1 2

输出 #1

NO
N/A
YES
YES
NO

注意

在第五个查询的第一个测试中:

1. 最初 Sam 告诉人们 $$$4$$$、$$$5$$$ 没有生病。
2. 在下一个查询中,Sam 询问患者 $$$5$$$ 的状态。从前面的查询我们知道,病人肯定没有生病。
3. 在下一个查询中,Sam 询问患者 $$$6$$$ 的状态。我们现在不知道有关该患者的任何信息。
4. 之后 Sam 告诉 $$$4$$$、$$$5$$$、$$$6$$$ 中存在一名病人。
5. 在下一个查询中,Sam 询问患者 $$$6$$$ 的状态。现在我们可以断定,这个病人肯定有病。