Score : $600$ points

问题描述

对于长度为 $M$ 的整数序列 $B=(B_1,B_2,\dots,B_M)$ 和 $C=(C_1,C_2,\dots,C_M)$，其中所有元素均为非负整数，定义它们的 异或和 $S(B,C)$ 为长度也为 $M$ 的由非负整数组成的序列 $(B_1\oplus C_1, B_2\oplus C_2, ..., B_{M}\oplus C_{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$ 个到第 $j$ 个元素组成的连续子序列。

你将收到 $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))$ 在字典序上 严格小于 $A(e, f)$，则打印 Yes；否则打印 No。

什么是按位异或运算？两个整数 $a$ 和 $b$ 的 exclusive logical sum（异或）$a \oplus b$ 定义如下：

• 在二进制表示中，$a \oplus b$ 中的 $2^k$ 位（$k \geq 0$）是 $1$ 当且仅当在 $a$ 和 $b$ 的二进制表示中恰好有一个的 $2^k$ 位为 $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$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

For sequences $B=(B_1,B_2,\dots,B_M)$ and $C=(C_1,C_2,\dots,C_M)$, each of length $M$, consisting of non-negative integers, let the XOR sum $S(B,C)$ of $B$ and $C$ be defined as the sequence $(B_1\oplus C_1, B_2\oplus C_2, ..., B_{M}\oplus C_{M})$ of length $M$ consisting of non-negative integers. Here, $\oplus$ represents bitwise XOR.
For instance, if $B = (1, 2, 3)$ and $C = (3, 5, 7)$, we have $S(B, C) = (1\oplus 3, 2\oplus 5, 3\oplus 7) = (2, 7, 4)$.

You are given a sequence $A = (A_1, A_2, \dots, A_N)$ of non-negative integers. Let $A(i, j)$ denote the contiguous subsequence composed of the $i$-th through $j$-th elements of $A$.
You will be given $Q$ queries explained below and asked to process all of them.

Each query gives you integers $a$, $b$, $c$, $d$, $e$, and $f$, each between $1$ and $N$, inclusive. These integers satisfy $a \leq b$, $c \leq d$, $e \leq f$, and $b-a=d-c$. If $S(A(a, b), A(c, d))$ is strictly lexicographically smaller than $A(e, f)$, print Yes; otherwise, print No.

What is bitwise XOR? The exclusive logical sum $a \oplus b$ of two integers $a$ and $b$ is defined as follows.

• The $2^k$'s place ($k \geq 0$) in the binary notation of $a \oplus b$ is $1$ if exactly one of the $2^k$'s places in the binary notation of $a$ and $b$ is $1$; otherwise, it is $0$.

For example, $3 \oplus 5 = 6$ (In binary notation: $011 \oplus 101 = 110$). What is lexicographical order on sequences?

A sequence $A = (A_1, \ldots, A_{|A|})$ is said to be strictly lexicographically smaller than a sequence $B = (B_1, \ldots, B_{|B|})$ if and only if 1. or 2. below is satisfied.

1. $|A|<|B|$ and $(A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|})$.
2. There is an integer $1\leq i\leq \min\{|A|,|B|\}$ that satisfies both of the following.
   • $(A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})$.
   • $A_i < B_i$.

Constraints

• $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$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format, where $\text{query}_i$ represents the $i$-th query:

$N$ $Q$

$A_1$ $A_2$ $\dots$ $A_N$

$\text{query}_1$

$\text{query}_2$

$\vdots$

$\text{query}_Q$

The queries are in the following format:

$a$ $b$ $c$ $d$ $e$ $f$

Output

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.

Sample Input 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

Sample Output 1

No
No
Yes
No
Yes

For the first query, we have $A(1, 3) = (1, 2, 3)$ and $A(2, 4) = (2, 3, 1)$, so $S(A(1,3),A(2,4)) = (1 \oplus 2, 2 \oplus 3, 3 \oplus 1) = (3, 1, 2)$. This is lexicographcially larger than $A(1, 4) = (1, 2, 3, 1)$, so the answer is No.
For the second query, we have $S(A(1,2),A(2,3)) = (3, 1)$ and $A(3,4) = (3, 1)$, which are equal, so the answer is No.

Sample Input 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

Sample Output 2

Yes
Yes
Yes
Yes
No
No
No
No
No
No

update @ 2024/3/10 11:34:20