AT_abc274_h [ABC274Ex] XOR Sum of Arrays

题目描述

对于两个长度为 $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，表示该询问的答案。

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #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

说明/提示

样例一：

对于第一个询问，$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.