Масив і XOR#229

Масив і XOR

4 секунди

512 мегабайтів

Складна

Задано ціле число $m$ , масив невід'ємних цілих чисел $a$ довжини $n$ та $q$ запитів виду $l_{i}$ l_i, $r_{i}$ r_i. Всі елементи масиву $a$ менші за $2^{m}$ 2^m.

Визначимо функцію $f_{i} (x) = min_{j \in [l_{i}, r_{i}]} (a_{j} \oplus x)$ f_i(x) = \min_{j \in [l_i, r_i]} (a_j \oplus x), де $\oplus$ позначає операцію побітового виключного АБО. Для кожного запиту вам потрібно знайти значення $max_{x \in {0, 1, \dots, 2^{m} - 1}} f_{i} (x)$ \max_{x \in \{0, 1, \ldots, 2^m-1\}} f_i(x).

Побітове виключне АБО невід'ємних цілих чисел $a$ та $b$ $(a \oplus b)$ (a \oplus b) дорівнює невід'ємному цілому числу, у якого у двійковому записі на певній позиції знаходиться одиниця тоді і тільки тоді, коли у двійкових записах $a$ та $b$ на цій позиції знаходяться різні значення. Наприклад, $3_{10} \oplus 5_{10} = 001 1_{2} \oplus 010 1_{2} = 011 0_{2} = 6_{10}$ 3_{10} \oplus 5_{10} = 0011_{2} \oplus 0101_{2} = 0110_{2} = 6_{10}.

Вхідні дані

У першому рядку задано три цілі числа $n$ , $q$ , $m$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5, $1 \leq q \leq 5 \cdot 1 0^{5}$ 1 \le q \le 5 \cdot 10^5, $1 \leq m \leq 50$ 1 \le m \le 50) — довжина масиву, кількість запитів та обмеження на елементи масиву відповідно.

У другому рядку задано $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n ( $0 \leq a_{i} < 2^{m}$ 0 \le a_i < 2^m) — елементи масиву.

У наступних $q$ рядках задано по два цілі числа $l_{i}$ l_i, $r_{i}$ r_i ( $1 \leq l_{i} \leq r_{i} \leq n$ 1 \le l_i \le r_i \le n) — параметри $i$ -го запиту.

Вихідні дані

Для $i$ -го запиту в окремому рядку виведіть одне ціле число — значення $max_{x \in {0, 1, \dots, 2^{m} - 1}} f_{i} (x)$ \max_{x \in \{0, 1, \ldots, 2^m-1\}} f_i(x).

Приклади

Приклад 1

Примітка

Розглянемо перший запит.

$f_{1} (0) = min (1 \oplus 0, 3 \oplus 0, 2 \oplus 0, 7 \oplus 0, 1 \oplus 0) = min (1, 3, 2, 7, 1) = 1$ f_1(0)=\min(1 \oplus 0, 3 \oplus 0, 2 \oplus 0, 7 \oplus 0, 1 \oplus 0)=\min(1, 3, 2, 7, 1)=1

$f_{1} (1) = min (1 \oplus 1, 3 \oplus 1, 2 \oplus 1, 7 \oplus 1, 1 \oplus 1) = min (0, 2, 3, 6, 0) = 0$ f_1(1)=\min(1 \oplus 1, 3 \oplus 1, 2 \oplus 1, 7 \oplus 1, 1 \oplus 1)=\min(0, 2, 3, 6, 0)=0

$f_{1} (2) = min (1 \oplus 2, 3 \oplus 2, 2 \oplus 2, 7 \oplus 2, 1 \oplus 2) = min (3, 1, 0, 5, 3) = 0$ f_1(2)=\min(1 \oplus 2, 3 \oplus 2, 2 \oplus 2, 7 \oplus 2, 1 \oplus 2)=\min(3, 1, 0, 5, 3)=0

$f_{1} (3) = min (1 \oplus 3, 3 \oplus 3, 2 \oplus 3, 7 \oplus 3, 1 \oplus 3) = min (2, 0, 1, 4, 2) = 0$ f_1(3)=\min(1 \oplus 3, 3 \oplus 3, 2 \oplus 3, 7 \oplus 3, 1 \oplus 3)=\min(2, 0, 1, 4, 2)=0

$f_{1} (4) = min (1 \oplus 4, 3 \oplus 4, 2 \oplus 4, 7 \oplus 4, 1 \oplus 4) = min (5, 7, 6, 3, 5) = 3$ f_1(4)=\min(1 \oplus 4, 3 \oplus 4, 2 \oplus 4, 7 \oplus 4, 1 \oplus 4)=\min(5, 7, 6, 3, 5)=3

$f_{1} (5) = min (1 \oplus 5, 3 \oplus 5, 2 \oplus 5, 7 \oplus 5, 1 \oplus 5) = min (4, 6, 7, 2, 4) = 2$ f_1(5)=\min(1 \oplus 5, 3 \oplus 5, 2 \oplus 5, 7 \oplus 5, 1 \oplus 5)=\min(4, 6, 7, 2, 4)=2

$f_{1} (6) = min (1 \oplus 6, 3 \oplus 6, 2 \oplus 6, 7 \oplus 6, 1 \oplus 6) = min (7, 5, 4, 1, 7) = 1$ f_1(6)=\min(1 \oplus 6, 3 \oplus 6, 2 \oplus 6, 7 \oplus 6, 1 \oplus 6)=\min(7, 5, 4, 1, 7)=1

$f_{1} (7) = min (1 \oplus 7, 3 \oplus 7, 2 \oplus 7, 7 \oplus 7, 1 \oplus 7) = min (6, 4, 5, 0, 6) = 0$ f_1(7)=\min(1 \oplus 7, 3 \oplus 7, 2 \oplus 7, 7 \oplus 7, 1 \oplus 7)=\min(6, 4, 5, 0, 6)=0

Відповідь на цей запит дорівнює $max_{x \in {0, 1, \dots, 2^{3} - 1}} f_{1} (x) = max (1, 0, 0, 0, 3, 2, 1, 0) = 3$ \max_{x \in \{0, 1, \ldots, 2^3-1\}} f_1(x) = \max(1, 0, 0, 0, 3, 2, 1, 0) = 3.

Оцінювання

( $4$ бали): $n \leq 100$ n \le 100, $q \leq 100$ q \le 100, $m \leq 10$ m \le 10;
( $17$ балів): $q = 1$ q=1, $l_{1} = 1$ l_1=1, $r_{1} = n$ r_1=n;
( $16$ балів): $q \leq 2 \cdot 1 0^{5}$ q \le 2 \cdot 10^5; $a_{i} \leq a_{i + 1}$ a_i \le a_{i+1} для $1 \leq i < n$ 1 \le i < n;
( $17$ балів): $n \leq 1 0^{4}$ n\le 10^4, $q \leq 1 0^{4}$ q \le 10^4;
( $26$ балів): $n \leq 5 \cdot 1 0^{4}$ n \le 5 \cdot 10^4, $m \leq 30$ m \le 30;
( $20$ балів): без додаткових обмежень.