← 返回题目列表

AtCoder · abc424_f

I. 添加和弦

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

分数: 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