Это сложная версия задачи. Единственное различие между двумя версиями заключается в наборе допустимых значений для начального массива и для $$$x$$$ в операциях типа $$$1$$$. В этой версии все эти значения принадлежат отрезку $$$[-10^9, 10^9]$$$. Совершать взломы можно только в том случае, если решены обе версии задачи.
Перед своей последней миссией Ктолли задаёт Виллему три вопроса.
Второй вопрос таков: что останется, если небо действительно достигнет своего конца?
Виллем не может ответить ей напрямую. Вместо этого он открывает хронику, содержащую $$$n$$$ записей, пронумерованных от $$$1$$$ до $$$n$$$. Каждая запись содержит целое число: положительное значение обозначает надежду, а отрицательное — отчаяние.
Начальное содержимое хроники образует массив $$$a_1,a_2,\ldots,a_n$$$, называемый версией $$$0$$$. Затем Ктолли выполняет $$$q$$$ операций. Для каждого $$$1\le i\le q$$$ $$$i$$$-я операция создаёт новую версию $$$i$$$ на основе версии $$$i-1$$$.
Каждая операция относится к одному из следующих четырёх типов:
Если операция относится к типу $$$1$$$, $$$2$$$ или $$$3$$$, указанное изменение применяется к версии $$$i-1$$$ для получения версии $$$i$$$. Операция типа $$$4$$$ не изменяет массив, поэтому версия $$$i$$$ совпадает с версией $$$i-1$$$.
Операции закодированы и должны обрабатываться по порядку. Их декодирование зависит от $$$\mathrm{lastans}$$$ (ответа на предыдущий вопрос), который обновляется после каждой операции типа $$$4$$$.
Помогите Виллему ответить на каждую операцию типа $$$4$$$.
$$$^{\text{∗}}$$$Массив $$$c$$$ является подмассивом массива $$$b$$$, если $$$c$$$ может быть получен из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных содержатся два целых числа $$$n$$$ и $$$q$$$ ($$$1\le n,q\le5\cdot10^5$$$) — длина массива и количество операций.
Во второй строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\le a_i\le 10^9$$$) — массив в версии $$$0$$$.
Каждая из следующих $$$q$$$ строк описывает одну операцию в одном из следующих кодированных форматов: Первое целое число в строке — тип операции.
Операции закодированы и должны обрабатываться по порядку. Их декодирование зависит от значения $$$\mathrm{lastans}$$$.
Изначально $$$\mathrm{lastans}=0$$$. После вычисления результата операции типа $$$4$$$ установите $$$\mathrm{lastans}$$$ равным остатку от деления её результата на $$$2^{64}$$$. Операции всех остальных типов оставляют $$$\mathrm{lastans}$$$ без изменений.
Для каждой закодированной координаты $$$y$$$ определим $$$d(y)=\left(\left(y\oplus\mathrm{lastans}\right)\bmod n\right)+1$$$. Здесь, $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.
Тип операции не кодируется. Не забудьте обновить $$$\mathrm{lastans}$$$ после выполнения каждой операции типа $$$4$$$.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5\cdot10^5$$$.
Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$5\cdot10^5$$$.
Для каждой операции типа $$$4$$$ выведите одно целое число — максимальную сумму непустого подмассива последовательности значений в позиции $$$p$$$ во всех версиях, предшествующих этой операции.
24 82 -3 1 -24 12 18446744073709551613 184467440737095516154 184467440737095516123 2 11 2 0 -44 22 8 104 103 61 -2 34 01 0 3 -14 32 6 73 7 44 7
-3394162
В первом наборе входных данных для первой операции $$$\mathrm{lastans}=0$$$, поэтому закодированная координата $$$1$$$ декодируется в позицию $$$2$$$. Рассматривается только версия $$$0$$$. Значение в позиции $$$2$$$ равно $$$-3$$$, следовательно, ответ равен $$$-3$$$.
Теперь $$$\mathrm{lastans}=2^{64}-3=18\,446\,744\,073\,709\,551\,613$$$. Следовательно, закодированный интервал $$$[18\,446\,744\,073\,709\,551\,613,18\,446\,744\,073\,709\,551\,615]$$$ декодируется в $$$[1,3]$$$, а закодированная координата $$$18\,446\,744\,073\,709\,551\,612$$$ декодируется в позицию $$$2$$$.
До второго запроса значения в позиции $$$2$$$ в версиях $$$0$$$, $$$1$$$ и $$$2$$$ равны $$$-3$$$, $$$-3$$$ и $$$3$$$ соответственно. Максимальная сумма их непустых подмассивов равна $$$3$$$.
До третьего запроса значения в позиции $$$2$$$ в версиях $$$0,1,\ldots,5$$$ образуют последовательность $$$[-3,-3,3,3,3,-4]$$$. Три последовательных значения, равные $$$3$$$, образуют подмассив с суммой $$$9$$$.
Обратите внимание, что первый, второй и третий запросы создают версии $$$1$$$, $$$3$$$ и $$$6$$$ соответственно, хотя они и не изменяют массив.
Во втором наборе входных данных первый запрос касается позиции $$$1$$$, поэтому его ответом является $$$1$$$. Тогда $$$\mathrm{lastans}=1$$$, и закодированная операция $$$\texttt{1 0 3 -1}$$$ декодируется в $$$\texttt{1 2 3 -1}$$$.
Перед вторым запросом значения в позиции $$$3$$$ в версиях $$$0$$$, $$$1$$$ и $$$2$$$ равны $$$3$$$, $$$3$$$ и $$$-1$$$ соответственно, поэтому ответ равен $$$6$$$.
После этого $$$\mathrm{lastans}=6$$$. Кодированные операции $$$\texttt{2 6 7}$$$ и $$$\texttt{3 7 4}$$$ декодируются в $$$\texttt{2 1 2}$$$ и $$$\texttt{3 2 3}$$$ соответственно. До последнего запроса значения в позиции $$$2$$$ в версиях $$$0,1,\ldots,5$$$ образуют последовательность $$$[-2,-2,-1,-1,1,1]$$$, максимальная сумма непустого подмассива которой равна $$$2$$$.
| Codeforces Round 1116 (Div. 1) |
|---|
| Закончено |
