E2. Аманожаку и последовательность (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Динь-Динь неравенства
— Taboo Japan Disentanglement

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии $$$1\le q \le 3\cdot 10^5$$$ и $$$1\le\mathrm{op}\le2$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Для последовательности $$$s$$$ обозначим через $$$|s|$$$ её длину.

Для целочисленной неотрицательной последовательности $$$c$$$ определим $$$f(c)$$$ как сумму квадратов её префиксных сумм: $$$$$$ f(c)=\sum_{i=1}^{|c|}\left(\sum_{j=1}^{i} c_j\right)^2. $$$$$$

Теперь определим $$$g(b,m)$$$ следующим образом.

Пусть $$$b$$$ — целочисленная последовательность, такая что для каждого $$$i$$$ выполнено $$$b_i\ge -1$$$, а $$$m$$$ — целое неотрицательное число. Целочисленная неотрицательная последовательность $$$c$$$ называется допустимой для $$$(b,m)$$$, если выполнены все следующие условия:

  • $$$|c|=|b|$$$;
  • $$$\sum_{i=1}^{|c|} c_i=m$$$;
  • для каждого $$$1\le i\le |b|$$$, если $$$b_i\ge 0$$$, то $$$c_i=b_i$$$; иначе, если $$$b_i=-1$$$, то $$$c_i$$$ может быть любым неотрицательным целым числом.

Значение $$$g(b,m)$$$ определяется как сумма $$$f(c)$$$ по всем допустимым последовательностям $$$c$$$ для $$$(b,m)$$$. Если такой последовательности не существует, то $$$g(b,m)=0$$$.

Вам дан массив $$$a$$$ длины $$$n$$$, где $$$a_i\ge -1$$$, и $$$q$$$ запросов двух типов:

  • По двум целым числам $$$p$$$ и $$$v$$$ присвоить $$$a_p$$$ значение $$$v$$$.
  • По трём целым числам $$$l$$$, $$$r$$$ и $$$m$$$ вычислить $$$g([a_l,a_{l+1},\ldots,a_r],m)$$$ по модулю $$$998\,244\,353$$$, где $$$[a_l,a_{l+1},\ldots,a_r]$$$ обозначает подмассив$$$^{\text{∗}}$$$ массива $$$a$$$ с позиции $$$l$$$ по позицию $$$r$$$.

$$$^{\text{∗}}$$$Массив $$$a$$$ является подмассивом массива $$$b$$$, если $$$a$$$ может быть получен из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Для каждого набора входных данных первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1\leq n\leq 3\cdot 10^5$$$, $$$1\leq q\leq 3\cdot 10^5$$$).

Во второй строке содержится $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$-1\leq a_i\leq 10^6$$$).

Затем следуют $$$q$$$ строк. Каждая строка описывает запрос в одном из следующих форматов. Первое целое число $$$\textrm{op}$$$ равно $$$1$$$ или $$$2$$$.

  • $$$1\,p\,v$$$: присвоить $$$a_p$$$ значение $$$v$$$ ($$$1\leq p\leq n$$$, $$$-1\leq v\leq 10^6$$$);
  • $$$2\,l\,r\,m$$$: вычислить $$$g([a_l,a_{l+1},\ldots,a_r],m)$$$ по модулю $$$998\,244\,353$$$ ($$$1\leq l\leq r\leq n$$$, $$$0\leq m\leq 10^6$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$3\cdot 10^5$$$.

Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$3\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных для каждого запроса второго типа выведите на отдельной строке значение $$$g([a_l,a_{l+1},\ldots,a_r],m)$$$ по модулю $$$998\,244\,353$$$.

Пример
Входные данные
2
5 7
4 -1 7 6 -1
2 2 2 2
1 3 8
2 3 3 0
2 4 5 8
1 5 7
2 3 5 21
2 3 5 22
4 6
-1 -1 -1 -1
2 1 1 4
2 1 2 5
2 1 3 6
2 1 4 7
1 3 3
2 1 4 5
Выходные данные
4
0
100
701
0
16
205
1736
12180
286
Примечание

В первом наборе входных данных:

В первом запросе $$$l=r=2$$$ и $$$m=2$$$. Подмассив равен $$$[a_2]=[-1]$$$, поэтому единственная допустимая последовательность — $$$c=[2]$$$. Следовательно, ответ равен $$$2^2=4$$$.

В четвёртом запросе $$$l=4$$$, $$$r=5$$$, и $$$m=8$$$. Подмассив равен $$$[a_4,a_5]=[6,-1]$$$. Поскольку $$$c_1$$$ фиксирован и равен $$$6$$$, а $$$c_1+c_2=m$$$, получаем $$$c=[6,2]$$$. Префиксные суммы равны $$$6$$$ и $$$8$$$, поэтому $$$$$$ f(c)=6^2+(6+2)^2=36+64=100. $$$$$$

Во втором наборе входных данных:

Во втором запросе подмассив равен $$$[a_1,a_2]=[-1,-1]$$$. Все допустимые последовательности удовлетворяют $$$c_1+c_2=5$$$ при $$$c_1,c_2\ge 0$$$, а именно $$$[0,5],[1,4],\ldots,[5,0]$$$. Сумма $$$f(c)$$$ по всем таким последовательностям равна $$$205$$$.