Сворачивание XOR на отрезках

Сложная

Возьмём непустой блок чисел и будем «сворачивать» его: одновременно заменим каждое число, кроме последнего, на XOR его самого и следующего за ним, а последнее число выбросим. Повторяем, пока не останется одно число — это и есть **результат сворачивания** блока. Например, [6, 3, 5] → [5, 6] → [3], результат 3. Блок из одного числа сворачивается сам в себя. Дан массив values и список запросов ranges, где ranges[i] = [l, r]. Для каждого запроса найдите наибольший результат сворачивания среди всех непрерывных блоков, целиком лежащих в values[l..r] (включительно). Верните список ответов в порядке запросов.

Пример 1

values=[6, 3, 5], ranges=[[0, 1], [0, 2], [2, 2]] → [6, 6, 5]

В отрезке [0, 1] блоки [6], [3] и [6, 3] дают 6, 3 и 6 XOR 3 = 5 — максимум 6. Весь массив [6, 3, 5] сворачивается в [5, 6], затем в 3, а блок [3, 5] даёт 6 — максимум снова 6. Отрезок [2, 2] — это одно число 5.

Пример 2

values=[1, 2, 4, 8], ranges=[[0, 3], [1, 2]] → [15, 6]

Весь массив сворачивается так: [1, 2, 4, 8] → [3, 6, 12] → [5, 10] → [15], и 15 — лучший результат в первом запросе. Во втором запросе блок [2, 4] даёт 6.

Ограничения

1 ≤ len(values) ≤ 2000
0 ≤ values[i] ≤ 2³¹ - 1
1 ≤ len(ranges) ≤ 10⁵
0 ≤ l ≤ r < len(values)

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Array Dynamic Programming

Вход

values=[6, 3, 5], ranges=[[0, 1], [0, 2], [2, 2]]

Ожидается

[6, 6, 5]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 57 тестов на сервере, включая скрытые.