Codeforces Round 830 (Div. 2) |
---|
Закончено |
Это сложная версия задачи. Единственное различие состоит в том, что в этой версии $$$q = n$$$.
Вам дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$.
Стоимостью подотрезка массива $$$[l, r]$$$, $$$1 \leq l \leq r \leq n$$$, назовем величину $$$f(l, r) = \operatorname{sum}(l, r) - \operatorname{xor}(l, r)$$$, где $$$\operatorname{sum}(l, r) = a_l + a_{l+1} + \ldots + a_r$$$, а $$$\operatorname{xor}(l, r) = a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$$$ ($$$\oplus$$$ обозначает побитовое исключающее ИЛИ).
У вас будет $$$q$$$ запросов. Каждый запрос задается парой чисел $$$L_i$$$, $$$R_i$$$, где $$$1 \leq L_i \leq R_i \leq n$$$. Вам нужно найти подотрезок $$$[l, r]$$$, $$$L_i \leq l \leq r \leq R_i$$$ с максимальным значением $$$f(l, r)$$$. Если ответов несколько, то среди них нужно найти подотрезок с минимальной длиной, то есть минимальным значением $$$r - l + 1$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n \leq 10^5$$$, $$$q = n$$$) — длину массива и количество запросов.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — элементы массива.
$$$i$$$-я из следующих $$$q$$$ строк каждого набора входных данных содержит два целых числа $$$L_i$$$ и $$$R_i$$$ ($$$1 \leq L_i \leq R_i \leq n$$$) — границы, в которых нужно найти отрезок.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Гарантируется, что $$$L_1 = 1$$$ и $$$R_1 = n$$$.
Для каждого набора входных данных выведите $$$q$$$ пар чисел $$$L_i \leq l \leq r \leq R_i$$$, таких что значение $$$f(l, r)$$$ максимально, а среди таких длина $$$r - l + 1$$$ минимальна. Если существует несколько правильных ответов, выведите любой из них.
61 101 12 25 101 22 23 30 2 41 31 22 34 40 12 8 31 41 32 42 35 521 32 32 32 101 51 41 32 53 57 70 1 0 1 0 1 01 73 62 51 44 72 62 7
1 1 1 1 2 2 1 1 1 1 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 3 4 2 4 4 6 2 4 2 4 4 6 2 4 2 4
Во всех наборах входных данных рассматривается первый запрос.
В первом наборе входных данных $$$f(1, 1) = 0 - 0 = 0$$$.
Во втором наборе входных данных $$$f(1, 1) = 5 - 5 = 0$$$, $$$f(2, 2) = 10 - 10 = 0$$$. Заметим, что $$$f(1, 2) = (10 + 5) - (10 \oplus 5) = 0$$$, но нам среди максимальных значений $$$f(l, r)$$$ нужно найти подотрезок с минимальной длиной. Поэтому правильными ответами будут только отрезки $$$[1, 1]$$$ и $$$[2, 2]$$$.
В четвертом наборе входных данных $$$f(2, 3) = (12 + 8) - (12 \oplus 8) = 16$$$.
В пятом наборе входных данных есть два правильных ответа, так как $$$f(2, 3) = f(3, 4)$$$ и их длины равны.
Название |
---|