← 返回题目列表

Codeforces · 2228/E2

E2. 天野雀和序列(硬版)

中文机器翻译题面 查看原题

不平等的小叮当
— 禁忌日本解脱

这是问题的困难版本。版本之间的区别在于,在这个版本中,$$$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$$$ 为整数序列,使得 $$$b_i\ge -1$$$ 对于每个 $$$i$$$,并令 $$$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$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。

输入

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