分数: 550 点
问题陈述
给定长度序列 N, A=(A_1,A_2,\ldots,A_N) 和 B=(B_1,B_2,\ldots,B_N).
还给你 Q 查询按顺序处理。
查询分为三种类型:
1 l r x:添加 x 到每个 A_l, A_{l+1}, \ldots, A_r.2 l r x:添加 x 到每个 B_l, B_{l+1}, \ldots, B_r.3 l r: 打印余数 \displaystyle\sum_{i=l}^r (A_i\times B_i) 除以 998244353.
约束
- 1\leq N,Q\leq 2\times 10^5
- 0\leq A_i,B_i\leq 10^9
- 1\leq l\leq r\leq N
- 1\leq x\leq 10^9
- 所有输入值均为整数。
- 至少有一个第三类型的查询。
输入
输入由标准输入按以下格式给出。在这里, \mathrm{query}_i (1\leq i\leq Q) 是 i- 要处理的第一个查询。
N Q
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
每个查询均以以下格式之一给出:
1 l r x
2 l r x
3 l r
输出
如果有 K 第三类查询,打印 K 行。
的
树的 i- 第行 (1\leq i\leq K)应包含输出 i第三种类型的第一个查询。
示例输入 1
5 6 1 3 5 6 8 3 1 2 1 2 3 1 3 1 2 5 3 3 1 3 1 1 3 1 2 5 5 2 3 1 5
示例输出 1
16 25 84
最初, A=(1,3,5,6,8) 和 B=(3,1,2,1,2)。查询按以下顺序处理:
- 对于第一个查询,打印 (1\times 3)+(3\times 1)+(5\times 2)=16 模数 998244353,即 16.
- 对于第二个查询,添加 3 to A_2,A_3,A_4,A_5。现在 A=(1,6,8,9,11).
- 对于第三个查询,打印 (1\times 3)+(6\times 1)+(8\times 2)=25 模数 998244353,即 25.
- 对于第四个查询,添加 1 to A_1,A_2,A_3。现在 A=(2,7,9,9,11).
- 对于第五个查询,添加 2 to B_5。现在 B=(3,1,2,1,4).
- 对于第六个查询,打印 (2\times 3)+(7\times 1)+(9\times 2)+(9\times 1)+(11\times 4)=84 模数 998244353,即 84.
因此,第一、第二和第三行应包含 16, 25,和 84。
示例输入 2
2 3 1000000000 1000000000 1000000000 1000000000 3 1 1 1 2 2 1000000000 3 1 2
示例输出 2
716070898 151723988
确保打印模数总和 998244353 为第三类查询。