102747: [AtCoder]ABC274 Ex - XOR Sum of Arrays
Description
Score : $600$ points
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$.
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.
- $|A|<|B|$ and $(A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|})$.
- 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
Input
题意翻译
### 题目描述 对于两个长度为 $t$ 的非负整数序列 $x,y$，定义非负整数序列 $S(x,y)=(x_1\oplus y_1,x_2\oplus y_2,\dots,x_t\oplus y_t)$，其中 $\oplus$ 为按位异或（XOR）。 对于长度为 $k$ 的序列 $x$ 和长度为 $l$ 的序列 $y$，若 $x<y$，当且仅当满足以下条件之一： + $k<l$ 且 $(x_1,x_2,\dots,x_k)=(y_1,y_2,\dots,y_k)$。 + 存在 $i\in[1,\min\{k,l\}]$ 使得 $(x_1,x_2,\dots,x_{i-1})=(y_1,y_2,\dots,y_{i-1})$ 且 $x_i<y_i$。 对于长度为 $t$ 的序列 $x$，定义序列 $x_{i,j}=(x_i,x_{i+1},\dots,x_j)$，其中 $1\leq i\leq j\leq t$。 给你一个长度为 $n$ 的序列 $a$，共有 $m$ 次询问，每次询问给你 $b,c,d,e,f,g$，若 $S(a_{b,c},a_{d,e})<a_{f,g}$，输出 `Yes`，否则输出 `No`。 ### 输入格式 第一行两个整数 $n,m$，含义如题中所述。 第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。 接下来 $m$ 行，每行 $6$ 个整数 $b,c,d,e,f,g$，含义如题中所述。 ### 输出格式 对于每个询问，输出一行一个字符串 `Yes` 或 `No`，表示该询问的答案。 ### 数据范围与提示 样例一： 对于第一个询问，$a_{1,3}=(1,2,3),a_{2,4}=(2,3,1),a_{1,4}=(1,2,3,1),S(a_{1,3},a_{2,4})=(3,1,2)$。 对于第二个询问，$a_{1,2}=(1,2),a_{2,3}=(2,3),a_{3,4}=(3,1),S(a_{1,2},a_{2,3})=(3,1)$。 **数据范围：** 对于所有数据，$1\leq n\leq 5\times 10^5,1\leq m\leq 5\times 10^4,0\leq a_i\leq 10^{18},1\leq b\leq c\leq n,1\leq d\leq e\leq n,1\leq f\leq g\leq n$，保证 $c-b=e-d$。 Translate by Zek3L.Output
分数：$600$分
问题描述
对于长度为$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)$表示由$A$的第$i$个到第$j$个元素组成的一段连续子序列。
你将收到$Q$个查询，你需要处理所有的查询。
每个查询给你整数$a$、$b$、$c$、$d$、$e$和$f$，它们都在$1$到$N$之间，包括$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$的按位异或$a \oplus b$定义如下。- 在$a \oplus b$的二进制表示中，第$2^k$位（$k \geq 0$）为$1$，如果$a$和$b$的二进制表示中的第$2^k$位有一个为$1$；否则，它为$0$。
序列上的字典序是什么？
一个序列$A = (A_1, \ldots, A_{|A|})$被认为比序列$B = (B_1, \ldots, B_{|B|})$严格地字典序小，如果满足以下条件之一。
- $|A|<|B|$且$(A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|})$。
- 存在一个整数$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