CF2228E2.Amanojaku and Sequence (Hard Version)

Tinkerbell of Inequality

— Taboo Japan Disentanglement

This is the hard version of the problem. The difference between the versions is that in this version, $1\le q \le 3\cdot 10^5$ and $1\le\mathrm{op}\le2$. You can hack only if you solved all versions of this problem.

For a sequence $s$, let $|s|$ denote its length.

For a non-negative integer sequence $c$, define $f(c)$ as the sum of the squares of its prefix sums: $$ f(c)=\sum_{i=1}^{{|c|}\left(\sum_{j=1}}{i} c_j\right)^2. $$

Now define $g(b,m)$ as follows.

Let $b$ be an integer sequence such that $b_i\ge -1$ for every $i$, and let $m$ be a non-negative integer. A non-negative integer sequence $c$ is called valid for $(b,m)$ if all of the following conditions hold:

• $|c|=|b|$;
• $\sum_{i=1}^{|c|} c_i=m$;
• for every $1\le i\le |b|$, if $b_i\ge 0$, then $c_i=b_i$; otherwise, if $b_i=-1$, then $c_i$ may be any non-negative integer.

The value $g(b,m)$ is defined as the sum of $f(c)$ over all valid sequences $c$ for $(b,m)$. If there is no such sequence, then $g(b,m)=0$.

You are given an array $a$ of length $n$, where $a_i\ge -1$, and $q$ queries of the following two types:

• Given two integers $p$ and $v$, set $a_p$ to $v$.
• Given three integers $l$, $r$, and $m$, compute $g([a_l,a_{l+1},\ldots,a_r],m)$ modulo $998\,244\,353$, where $[a_l,a_{l+1},\ldots,a_r]$ denotes the subarray$^{\text{∗}}$ of $a$ from position $l$ to position $r$.

$^{\text{∗}}$An array $a$ is a subarray of an array $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

不等式的 tinkerbelle

——禁忌日本解耦问题

这是该问题的困难版本。两个版本的区别在于：在此版本中，$1\le q \le 3\cdot 10^5$ 且 $1\le\mathrm{op}\le2$。仅当您已解决该问题的所有版本时，才允许进行 hack。

对于一个序列 $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)$ 定义为所有关于 $(b,m)$ 的合法序列 $c$ 对应的 $f(c)$ 之和。若不存在这样的序列，则 $g(b,m)=0$。

给定一个长度为 $n$ 的数组 $a$，其中每个 $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]$ 表示数组 $a$ 从位置 $l$ 到位置 $r$ 的子数组$^{\text{∗}}$。

$^{\text{∗}}$ 若数组 $a$ 可通过从数组 $b$ 的开头删除若干（可能为零或全部）元素、并从结尾删除若干（可能为零或全部）元素而得到，则称 $a$ 是 $b$ 的一个子数组。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

For each test case, the first line contains two integers $n$ and $q$ ($1\leq n\leq 3\cdot 10^5$, $1\leq q\leq 3\cdot 10^5$).

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-1\leq a_i\leq 10^6$).

Then $q$ lines follow. Each line describes a query in one of the following format. The first integer $\textrm{op}$ is $1$ or $2$.

• $1\,p\,v$: set $a_p$ to $v$ ($1\leq p\leq n$, $-1\leq v\leq 10^6$);
• $2\,l\,r\,m$: compute $g([a_l,a_{l+1},\ldots,a_r],m)$ modulo $998\,244\,353$ ($1\leq l\leq r\leq n$, $0\leq m\leq 10^6$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot 10^5$.

It is guaranteed that the sum of $q$ over all test cases does not exceed $3\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例数量 $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$。

For each test case, for every query of the second type, output the value of $g([a_l,a_{l+1},\ldots,a_r],m)$ modulo $998\,244\,353$ on a line.

对于每个测试用例，对每一个第二类查询，输出 $g([a_l,a_{l+1},\ldots,a_r],m)$ 对 $998\,244\,353$ 取模的结果，每行一个。

In the first test case:

For the first query, $l=r=2$ and $m=2$. The subarray is $[a_2]=[-1]$, so the only valid sequence is $c=[2]$. Thus, the answer is $2^2=4$.

For the fourth query, $l=4$, $r=5$, and $m=8$. The subarray is $[a_4,a_5]=[6,-1]$. Since $c_1$ is fixed at $6$ and $c_1+c_2=m$, we obtain $c=[6,2]$. The prefix sums are $6$ and $8$, giving $$ f(c)=6^2+(6+2)2=36+64=100. $$

In the second test case:

For the second query, the subarray is $[a_1,a_2]=[-1,-1]$. All valid sequences satisfy $c_1+c_2=5$ with $c_1,c_2\ge 0$, namely $[0,5],[1,4],\ldots,[5,0]$. Summing $f(c)$ over all such sequences yields $205$.

在第一个测试用例中：

对于第一个查询，$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$。