CF2228E1 Amanojaku and Sequence (Easy Version)

不等式的小精灵 ——Taboo Japan Disentanglement 这是本题的简单版本。本题不同于难版本之处在于 $q=1$ 且 $\mathrm{op}=2$。只有当你解决了所有版本的问题后，才可以进行 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$ 满足以下所有条件，则称 $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$ 个如下类型的查询： - 给定三个整数 $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$ 个元素组成的子数组$^*$。 $^*$ 数组 $a$ 被称为数组 $b$ 的一个子数组，如果 $a$ 可以由 $b$ 删去开头若干（也可以不删）元素和结尾若干（也可以不删）元素得到。

每组测试数据包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。接下来为每组测试用例的描述。 每组测试用例的第一行包含两个整数 $n$ 和 $q$（$1\leq n\leq 3\cdot 10^5$，$q=1$）。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-1\leq a_i\leq 10^6$）。 接着 $q$ 行，每行描述一个查询，格式如下。第一个整数 $\textrm{op}$ 是 $2$。 - $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$。

对于每一组测试用例，对于每个类型二的查询，输出 $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 翻译