P7906 [Ynoi2005] rpxleqxq

You are given a sequence $a$ of length $n$ consisting of positive integers, and a constant $x$. Let $x \oplus y$ denote the bitwise XOR of $x$ and $y$. There are $q$ queries. Each query gives an interval $[l, r]$. You need to find how many pairs $(i, j)$ in this interval satisfy $i < j \land (a_i \oplus a_j) \le x$.

The first line contains two positive integers $n, x$, representing the length of the sequence and the given constant. The next line contains $n$ integers representing the sequence $a$. The third line contains a positive integer $q$, representing the number of queries. The next $q$ lines each contain two positive integers $l, r$, representing one query.

Output $q$ lines. Each line contains one integer, representing the answer.

Idea: Dpair, Solution: Dpair, Code: Dpair, Data: Dpair & nzhtl1477. For $1\%$ of the testdata, it is the sample. For another $19\%$ of the testdata, $n, q \le 100$. For another $19\%$ of the testdata, $n, q \le 1000$. For another $19\%$ of the testdata, $q \le 100$. For another $19\%$ of the testdata, $a_i, x \le 100$. For $100\%$ of the testdata, $1 \le n, a_i, x \le 2 \times 10^5$, and $1 \le q \le 10^6$. Translated by ChatGPT 5