CF2228E2 Amanojaku and Sequence (Hard Version)

不等式的小精灵 —— “禁忌日本解绑” 这是该题目的难度较高版本。此版本与另一版本的区别在于 $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)$ 的值定义为所有合法序列 $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)\bmod 998\,244\,353$，其中 $[a_l,a_{l+1},\ldots,a_r]$ 表示 $a$ 的第 $l$ 到第 $r$ 个元素组成的子数组。 注：一个数组 $a$ 是数组 $b$ 的一个子数组，如果 $a$ 可以通过从 $b$ 的开头和结尾各删除若干（包括 $0$ 或全部）元素得到。

每组测试数据包含多组用例。第一行输入用例组数 $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)\bmod 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$。

对于每组用例的每一个 2 型查询，输出一行结果，为 $g([a_l,a_{l+1},\ldots,a_r],m)$ 在 $998\,244\,353$ 下的余数。

在第一组用例中： 第一个查询，$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$。 由 ChatGPT 5 翻译