← 返回题目列表

AtCoder · abc357_f

I. 两个序列查询

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

分数: 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 为第三类查询。