AT_abc357_f [ABC357F] Two Sequence Queries

题目描述

给定长度为 $N$ 的数列 $A=(A_1,A_2,\ldots,A_N)$，$B=(B_1,B_2,\ldots,B_N)$。
有 $Q$ 个查询，请依次处理这些查询。

查询有以下 $3$ 种类型：

• 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$ 的余数。

输入格式

输入以如下格式从标准输入给出。这里，$\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$ 个第 $3$ 种类型的查询，则输出 $K$ 行。
第 $i$ 行（$1\leq i\leq K$）输出第 $i$ 个第 $3$ 种类型查询的答案。

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #2

2 3
1000000000 1000000000
1000000000 1000000000
3 1 1
1 2 2 1000000000
3 1 2

输出 #2

716070898
151723988

说明/提示

数据范围

• $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$
• 输入均为整数
• 至少存在一个第 $3$ 种类型的查询

样例解释 1

初始时，$A=(1,3,5,6,8)$，$B=(3,1,2,1,2)$。查询按如下顺序处理：

• 第 $1$ 个查询，输出 $(1\times 3)+(3\times 1)+(5\times 2)=16$，对 $998244353$ 取余为 $16$。
• 第 $2$ 个查询，将 $3$ 加到 $A_2,A_3,A_4,A_5$ 上。$A=(1,6,8,9,11)$。
• 第 $3$ 个查询，输出 $(1\times 3)+(6\times 1)+(8\times 2)=25$，对 $998244353$ 取余为 $25$。
• 第 $4$ 个查询，将 $1$ 加到 $A_1,A_2,A_3$ 上。$A=(2,7,9,9,11)$。
• 第 $5$ 个查询，将 $2$ 加到 $B_5$ 上。$B=(3,1,2,1,4)$。
• 第 $6$ 个查询，输出 $(2\times 3)+(7\times 1)+(9\times 2)+(9\times 1)+(11\times 4)=84$，对 $998244353$ 取余为 $84$。

因此，第 $1$、$2$、$3$ 行分别输出 $16$、$25$、$84$。

样例解释 2

请注意，第 $3$ 种类型的查询需要对 $998244353$ 取余。

由 ChatGPT 4.1 翻译