section>
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 theXOR 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.
- $|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 lexicographically 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
Obviously, it’s a hash problem. To determine which lexicographic order is larger, you can find the first \(i\) by binary division so that \(a_i\
e b_i\) and then determine the size of \(a_i\) and \(b_i\). Then in the bisection process, you only need to determine whether the two sequences are the same, and you can use hash to determine.
The official solution method is amazing. Here we refer to the AC program method used in most competitions.
First of all, if you change XOR to addition, you are using the classic Robin-Karp hash. Using a number \(x\) as a bit weight, define the hash value of a sequence \(a_1,a_2\cdots a_k\) as \(x^{k-1}a_1 + x^{k-2}a_2\ cdots xa_{k-1} + a_{k}\) This \(x\) can be chosen randomly. Then the hash value of the easy sequence \(a_1 + b_1,a_2 + b_2\cdots a_k + b_k\) is the hash value of the \(a\) sequence plus the hash value of the \(b\) sequence. Therefore, to determine whether they are the same, you can directly add the first two hash values to determine whether they are the same as the third sequence.
But what about XOR? If it is XOR, our hash will not work at all, because multiplication has no distributive law for XOR. We are looking for an operation that satisfies the distributive law for XOR, and we think of AND and OR, but they do not support powers.
This operation is matrix multiplication. Think of a binary as a row vector. As we all know, the form of normal matrix multiplication is $$c_{i,j}=\sum{a_{i,j}\times b_{j,k}}$$
Then modify it to $$c_{i,j}=\bigoplus a_{i,j}\and b_{j,k}$$\(\bigoplus\) still represents XOR, \(\and\) represents Bitwise AND.
According to the conclusion of the matrix, since bitwise AND has a distributive law for XOR, the resulting matrix actually has an associative law and a distributive law for XOR. So the method is to use a random 01 matrix as the bit weight. In this way, when hashing, we can directly XOR the hash values of the two sequences, which is equal to the hash value of the sequence after bitwise XOR.
But the complexity of such a matrix multiplication is \(log^3\), can’t it be counted as two points? Similar matrix multiplications that use bit operations as operations can mostly be bit-pressed. Observe the above formula, if \(a_{i,j}=1,c_i^=b_j\) (c,b have been compressed into binary). The complexity of matrix multiplication is reduced to \(log^2\)
In addition, since the matrix satisfies the distributive law, after preprocessing the power of the matrix, the hash value of the interval \([l,r]\) can be directly extracted like a normal hash. But I doubled it just to be on the safe side. This is more likely to be true.
#include<bits/stdc + + .h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N=5e5 + 5,M=63;
mt19937_64 gen(time(0));
struct matrix{
int a[M];
void init()
{
for(int i=0;i<M;i + + )
a[i]=1LL<<i;
}
matrix operator*(const matrix & amp;b)const{
matrix c;
memset(c.a,0,sizeof(c.a));
for(int i=0;i<M;i + + )
for(int j=0;j<M;j + + )
if(a[i]>>j &1)
c.a[i]^=b.a[j];
return c;
}
void operator=(matrix b){
for(int i=0;i<M;i + + )
a[i]=b.a[i];
}
}pw[25];
LL mul(LL x,matrix a)
{
LL ret=0;
for(int i=0;i<M;i + + )
if(x>>i &1)
ret^=a.a[i];
return ret;
}
LL x[N],st[25][N];
int n,q,a,b,c,d,e,f;
int main()
{
scanf("%d%d", & amp;n, & amp;q);
for(int i=0;i<M;i + + )
pw[0].a[i]=gen();
for(int i=1;i<=n;i + + )
scanf("%lld",x + i),st[0][i]=x[i];
for(int i=1;i<25;i + + )
pw[i]=pw[i-1]*pw[i-1];
for(int i=1;i<25;i + + )
for(int j=1;j + (1<<i)-1<=n;j + + )
st[i][j]=st[i-1][j]^mul(st[i-1][j + (1<<i-1)],pw[i-1]);
while(q--)
{
scanf("%d%d%d%d%d%d", & amp;a, & amp;b, & amp;c, & amp;d, & amp;e, & amp;f);
int l=0;
for(int i=24;i>=0;i--)
if(a + l + (1<<i)<=b + 1 & amp; & amp;e + l + (1<<i)<=f + 1 & amp; & amp;(st[i][ a + l]^st[i][c + l])==st[i][e + l])
l + =1<<i;
if(e + l>f)
printf("No\
");
else if(a + l>b)
printf("Yes\
");
else if((x[a + l]^x[c + l])<x[e + l])
printf("Yes\
");
else
printf("No\
");
}
}