分数: 525 点
问题陈述
有 N 点在圆上等距分布,编号 1,2,\dots,N 顺时针方向。
你被给予 Q 以下形式的查询;按顺序处理它们。
- 绘制连接点的线段 A_i 和 B_i。但是,如果该线段与已绘制的线段相交,则不要绘制它。
这里,保证 2Q 整数 A_1,\ldots,A_Q,B_1,\ldots,B_Q 都是不同的。
对于每个查询,回答该线段是否被绘制。
约束
- 2 \leq N \leq 10^6
- 1 \leq Q \leq 3\times 10^5
- 1 \leq A_i < B_i \leq N
- 的 2Q 整数 A_1,\ldots,A_Q,B_1,\ldots,B_Q 成对不同。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q A_1 B_1 A_2 B_2 \vdots A_Q B_Q
输出
输出 Q 行。
上 i第行,输出 Yes 如果,在 i-第一个查询,绘制了线段,并且 No 如果没有绘制。
示例输入 1
8 3 1 5 2 7 3 4
示例输出 1
Yes No Yes
通过查询,绘制出如图所示的段。
- 在 1-st 查询,线段连接点 绘制了 1 和 5 。
- 在 2-nd查询,线段连接点 2 和 7 未绘制,因为它与中绘制的线段相交 1-st 查询。
- 在 3-rd 查询,线段连接点 3 和 4 。

示例输入 2
999999 4 123456 987654 888888 999999 1 3 2 777777
示例输出 2
Yes No Yes No