AT_aalc001_p.Connect the Dots

省选/NOI-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

圆上有 2N2N 个顶点,按顺时针顺序依次编号为顶点 11、顶点 22、…\ldots、顶点 2N2N。

给定一个由 NN 个整数对组成的序列 ((A1,B1),(A2,B2),…,(AN,BN))((A_1,B_1),(A_2,B_2),\ldots,(A_N,B_N))。这 2N2N 个值 A1,…,AN,B1,…,BNA_1,\ldots,A_N,B_1,\ldots,B_N 互不相同。

处理 QQ 个查询。在第 jj 个查询中,给出整数 lj,rjl_j,r_j。判断是否能画出满足以下所有条件的曲线:

  • 对每个 i=lj,lj+1,…,rji=l_j,l_j+1,\ldots,r_j,画出一条连接顶点 AiA_i 和顶点 BiB_i 的曲线;
  • 每条曲线均位于圆内或圆周上;
  • 任意两条不同的曲线互不相交。

每个查询相互独立。一个查询中所画的曲线不影响其他查询。

输入格式

输入从标准输入中按以下格式给出:

NN QQ
A1A_1 B1B_1
A2A_2 B2B_2
⋮\vdots
ANA_N BNB_N
l1l_1 r1r_1
l2l_2 r2r_2
⋮\vdots
lQl_Q rQr_Q

输出格式

输出 QQ 行。

在第 jj 行中,如果能够为第 jj 个查询绘制满足条件的曲线,则输出 Yes,否则输出 No。

输入输出样例

  • 输入#1

    5 6
    1 10
    2 5
    3 4
    6 8
    7 9
    1 3
    2 4
    4 5
    1 5
    3 3
    3 4

    输出#1

    Yes
    Yes
    No
    No
    Yes
    Yes
  • 输入#2

    4 4
    1 5
    2 6
    3 4
    7 8
    1 2
    2 4
    1 3
    3 4

    输出#2

    No
    Yes
    No
    Yes

说明/提示

样例 1 解释:
对于查询 11,可以画出连接顶点 11 与 1010、顶点 22 与 55、以及顶点 33 与 44 的曲线,且这些曲线互不相交。

对于查询 33,连接顶点 66 与 88 的曲线和连接顶点 77 与 99 的曲线无法在不相交的情况下画出。

约束条件

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤Q≤2×1051 \leq Q \leq 2 \times 10^5
  • 1≤Ai<Bi≤2N1 \leq A_i \lt B_i \leq 2N
  • (A1,…,AN,B1,…,BN)(A_1,\ldots,A_N,B_1,\ldots,B_N) 是 (1,2,…,2N)(1,2,\ldots,2N) 的一个排列。
  • 1≤lj≤rj≤N1 \leq l_j \leq r_j \leq N
  • 输入中的所有数值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页