问题陈述
给你两个序列 A=(A_1,\ldots,A_N) 和 B=(B_1,\ldots,B_N) 长度 N.
处理给定的 Q 按顺序查询。 每个查询属于以下类型之一:
1 p x:设置 A_p to x.2 p x:设置 B_p to x.3 l r x:判断是否存在整数对 (i,j) 这样 l\leq i\leq j\leq r 和 A_i+A_{i+1}+\dots+A_j\equiv x \pmod 3。 如果存在,则打印最大值 B_i+B_{i+1}+\dots+B_j 其中 (i,j).
约束
- 1\leq N,Q \leq 2\times 10^5
- 0\leq A_i \leq 2
- -10^9\leq B_i \leq 10^9
- 对于第一种查询:
- 1\leq p \leq N
- 0\leq x \leq 2
- 对于第二类的每个查询:
- 1\leq p \leq N
- -10^9\leq x \leq 10^9
- 对于第三类的每个查询:
- 1\leq l\leq r \leq N
- 0\leq x \leq 2
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q
在这里, \mathrm{Query}_k\ (1\leq k\leq Q) 表示 k-第一个查询,采用以下格式之一:
1 p x
2 p x
3 l r x
输出
打印 c 行,其中 c 是第三类查询的数量。
的 k第行 (1\leq k \leq c) 应回应 k- 第三类查询,包含最大值 B_i+B_{i+1}+\dots+B_j 符合条件的配对中 (i,j) 如果存在这样的一对,或者 No 否则。
示例输入 1
3 5 0 1 2 3 12 -5 3 1 3 0 1 3 0 3 2 3 1 2 3 2 3 2 3 1
示例输出 1
10 12 14
- 1-st查询:有三个整数对 (i,j) 这样 1\leq i\leq j\leq 3 和 A_i+A_{i+1}+\dots+A_j\equiv 0 \pmod 3:即 (1,1),(1,3),和 (2,3)。 的价值观 B_i+B_{i+1}+\dots+B_j 是 分别为 3,10,和 7,分别打印最大值 10 其中。
- 2-nd 查询:设置 A_3 to 0.
- 3-rd查询:有两个整数对 (i,j) 这样 2\leq i\leq j\leq 3 和 A_i+A_{i+1}+\dots+A_j\equiv 1 \pmod 3:即 (2,2) 和 (2,3)。 的价值观 B_i+B_{i+1}+\dots+B_j 是 分别为 12 和 7,分别打印最大值 12 其中。
- 4第一个查询:设置 B_3 to 2.
- 5-第查询:有两个整数对 (i,j) 这样 2\leq i\leq j\leq 3 和 A_i+A_{i+1}+\dots+A_j\equiv 1 \pmod 3:即 (2,2) 和 (2,3)。 的价值观 B_i+B_{i+1}+\dots+B_j 是 分别为 12 和 14,分别打印最大值 14 其中。
示例输入 2
1 3 2 100 3 1 1 0 3 1 1 1 3 1 1 2
示例输出 2
No No 100
对于 1-st查询,没有整数对 (i,j) 这样 1\leq i\leq j\leq 1 和 A_i+A_{i+1}+\dots+A_j\equiv 0 \pmod 3.
示例输入 3
1 1 2 100 1 1 0
示例输出 3
可能没有第三类查询。
示例输入 4
10 10 1 1 2 0 0 2 0 2 0 0 -52 -52 14 -11 -2 -54 46 8 26 -17 3 1 9 2 2 8 71 1 10 1 2 9 86 1 5 2 3 7 7 0 3 4 5 0 2 10 100 2 1 -95 1 1 1
示例输出 4
80 46 -11