← 返回题目列表

AtCoder · past22_o

O. 最大范围总和

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

问题陈述

给你两个序列 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