ABC357F Two Sequence Queries

题目描述

问题陈述

给你长度为N A=( $A_1,A_2,A_3,\cdots,A_N$ )和B=( $B_1,B_2,B_3,\cdots,B_N$ )的序列。
您还得到了Q个查询，需要按顺序处理。

查询有三种类型：

• 1 l r x: 将x添加到 $A_{l}$,$A_{l+1}$​,…,$A_{r}$中。
• 2 l r x: 将x添加到$B_{l}$,$B_{l+1}$​,…,$B_{r}$中。
• 3 l r: 打印 $\sum_{i=l}^{r}$ ​($A_{i}$×$B_{i}$​)除以998244353的余数。

输入描述

第一行输入两个正整数N和Q

第二行输入N个整数，代表序列A，$A_1,A_2,A_3,\cdots,A_N$

第三行输入N个整数，代表序列B，$B_1,B_2,B_3,\cdots,B_N$

接下来Q行：Q个提问

数据范围：

• 1≤N,Q≤2× $10^{5}$
• 0≤Ai​,Bi​≤ $10^{9}$
• 1≤l≤r≤N
• 1≤x≤$10^{9}$

输出描述

如果有K个第三类查询，则打印K行查询到的答案。

提示

样例1解释：

最初为A=(1,3,5,6,8)和B=(3,1,2,1,2)。查询按以下顺序处理：

• 对于第一个查询，打印(1×3)+(3×1)+(5×2)=16%998244353，即16。
• 对于第二个查询，将3加到A2​,A3​,A4​,A5​。现在是A=(1,6,8,9,11)。
• 对于第三个查询，打印(1×3)+(6×1)+(8×2)=25%998244353，即25。
• 对于第四个查询，将1加到A1​,A2​,A3​。现在是=(2,7,9,9,11)。
• 对于第五个查询，将2添加到B5​。现为B=(3,1,2,1,4)。
• 对于第六个查询，打印(2×3)+(7×1)+(9×2)+(9×1)+(11×4)=84%998244353，即84。

因此，第一、第二和第三行应分别包含16、25和84。