AT_abc274_h.[ABC274Ex] XOR Sum of Arrays

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

对于两个长度为 $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

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

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.

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

首页