/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さ M の非負整数列 B=(B_1,B_2,\dots,B_M), C=(C_1,C_2,\dots,C_M) に対して、B と C の XOR 和 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 の連続部分列を A(i, j) と表します。
以下に説明するクエリが Q 個与えられるので全て処理してください。
各クエリでは 1 以上 N 以下の整数 a, b, c, d, e, f が与えられます。これらの整数は 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) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
数列の辞書順とは？
数列 A = (A_1, \ldots, A_{|A|}) が B = (B_1, \ldots, B_{|B|}) より辞書順で真に小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。
- |A|<|B| かつ (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}) である。
- ある整数 1\leq i\leq \min\{|A|,|B|\} が存在して、下記の 2 つがともに成り立つ。
- (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
1 番目のクエリについて、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 になります。
2 番目のクエリについて、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
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