← 返回题目列表

AtCoder · abc274_h

Ex. 数组的异或和

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

分数: 600 点

问题陈述

对于序列 B=(B_1,B_2,\dots,B_M) 和 C=(C_1,C_2,\dots,C_M),每个长度 M,由非负整数组成,令 异或和 S(B,C) of B 和 C 被定义为序列 (B_1\oplus C_1, B_2\oplus C_2, ..., B_{M}\oplus C_{M}) 长度 M 由非负整数组成。在这里, \oplus 表示按位异或。
例如,如果 B = (1, 2, 3) 和 C = (3, 5, 7),我们有 S(B, C) = (1\oplus 3, 2\oplus 5, 3\oplus 7) = (2, 7, 4).

给你一个序列 A = (A_1, A_2, \dots, A_N) 非负整数。让 A(i, j) 表示由以下组成的连续子序列 i-th 通过 j第一个元素 A.
你将得到 Q 查询解释如下,并要求处理所有这些查询。

每个查询都会为您提供整数 a, b, c, d, e,和 f,每个之间 1 和 N,包括在内。这些整数满足 a \leq b, c \leq d, e \leq f,和 b-a=d-c。如果 S(A(a, b), A(c, d)) is 严格 按字典顺序小于 A(e, f),打印 Yes;否则,打印 No.

什么是按位异或? 异或逻辑和 a \oplus b 两个整数 a 和 b 定义如下。
  • 的 2^k的地点 (k \geq 0) 的二进制表示法 a \oplus b is 1 如果恰好是其中之一 2^k在二进制表示法中的位置 a 和 b is 1;否则,就是 0.
例如, 3 \oplus 5 = 6 (二进制表示法: 011 \oplus 101 = 110).
序列的字典顺序是什么?

一个序列 A = (A_1, \ldots, A_{|A|}) 据说是 严格按字典顺序较小 比序列 B = (B_1, \ldots, B_{|B|}) 当且仅当满足以下 1. 或 2. 时。

  1. |A|<|B| 和 (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}).
  2. 有一个整数 1\leq i\leq \min\{|A|,|B|\} 满足以下两个条件。
    • (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1}).
    • A_i < B_i.

约束

  • 1 \leq N \leq 5 \times 10^5
  • 0 \leq A_i \leq 10^{18}
  • 1 \leq Q \leq 5 \times 10^4
  • 1 \leq a \leq b \leq N
  • 1 \leq c \leq d \leq N
  • 1 \leq e \leq f \leq N
  • b - a = d - c
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出,其中 \text{query}_i 代表 i第一个查询:

N Q
A_1 A_2 \dots A_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

查询采用以下格式:

a b c d e f

输出

打印 Q 行。的 i- 第行应包含以下问题的答案 i第一个查询。


示例输入 1

4 5
1 2 3 1
1 3 2 4 1 4
1 2 2 3 3 4
1 1 2 2 3 4
1 2 2 3 3 3
1 4 1 4 1 1

示例输出 1

No
No
Yes
No
Yes

对于第一个查询,我们有 A(1, 3) = (1, 2, 3) 和 A(2, 4) = (2, 3, 1),所以 S(A(1,3),A(2,4)) = (1 \oplus 2, 2 \oplus 3, 3 \oplus 1) = (3, 1, 2)。按字典顺序,这大于 A(1, 4) = (1, 2, 3, 1),所以答案是 No.
对于第二个查询,我们有 S(A(1,2),A(2,3)) = (3, 1) 和 A(3,4) = (3, 1),它们相等,所以答案是 No.


示例输入 2

10 10
725560240 9175925348 9627229768 7408031479 623321125 4845892509 8712345300 1026746010 4844359340 2169008582
5 6 5 6 2 6
5 6 1 2 1 1
3 8 3 8 1 6
5 10 1 6 1 7
3 4 1 2 5 5
7 10 4 7 2 3
3 6 1 4 7 9
4 5 3 4 8 9
2 6 1 5 5 8
4 8 1 5 1 9

示例输出 2

Yes
Yes
Yes
Yes
No
No
No
No
No
No