P10743 [SEERC 2020] AND = OR

An array $b$ is called a "good array" if and only if $b$ can be split into two non-empty subarrays such that the $\mathtt{OR}$ result of the first subarray is equal to the $\mathtt{AND}$ result of the second subarray. For example, for $\{1,7,3,11\}$, split it into $\{1,3\}$ and $\{7,11\}$. Then $1\ \mathtt{OR}\ 3 = 3$ and $7\ \mathtt{AND}\ 11 = 3$, so it is a good array. Now you are given an array $a$ of length $n$ and $q$ queries. In each query, given $[l,r]$, determine whether $\{a_l, a_{l+1},\ldots,a_{r-1},a_{r}\}$ is a good array.

The first line contains two integers $n\ (1 \leq n \leq 10^5)$ and $q\ (1 \leq q \leq 10^5)$. The second line contains $n$ integers representing the sequence $a\ (0\leq a_i \leq 2^{30}-1)$. The next $q$ lines each contain two integers $l,r\ (1 \leq l \leq r \leq n)$, representing a query.

For each query, if the subarray is good, output `YES`; otherwise output `NO`.

Translated by ChatGPT 5