#P17261. [2025年南开中学集训]梦境

[2025年南开中学集训]梦境

题目描述

小 F 猛然醒来,才觉是黄粱一梦。现实上他还在赛场上,他打开题面阅读起来:

给定两个长度为 n n 序列 a,b a,b 。

对于一段区间 l,r l,r 的权值为 ∑i=lraibi \sum_{i=l}^ra_ib_i 。

你需要进行 m m 次操作:

  1. a a 全局加。
  2. 查询一个区间,求它所有子区间(可以为空,此时权值为 0 0 )权值的最大值。

此刻你就是小 F,请你完成此题代码。

输入格式

第一行两个整数 n,m n,m 。

第二行 n n 个整数,第 i i 个整数为 ai a_i 。

第三行 n n 个整数,第 i i 个整数为 bi b_i 。

注意 b b 的取值为 1 1 或 −1 -1 。

之后 m m 行,每行一个操作:

  • 1 x 1\ x : a a 序列所有数加上 x x 。
  • 2 l r 2\ l\ r :查询区间 [l,r] [l,r] 。

输出格式

对于每个询问,输出一个数表示答案。

输入输出样例 #1

输入 #1

7 7
1 2 3 4 5 6 7
-1 1 -1 1 -1 1 -1
2 3 5
1 -4
2 1 3
2 5 7
2 7 7
1 5
2 1 7

输出 #1

4
3
2
0
7

对于所有测试点,

  • 1≤n,m≤5×105 1\le n,m\le 5\times 10^5 , −106≤ai,x≤106 -10^6\le a_i,x\le 10^6 , bi=±1 b_i=\pm 1 。

子任务 1(10分): 1≤n,m≤103 1\le n,m\le 10^3 。

子任务 2(15分): 1≤n≤104 1\le n\le 10^4 , 1≤m≤5×105 1\le m\le 5\times 10^5 。

子任务 3(35分): 1≤n,m≤105 1\le n,m\le 10^5 。

子任务 4(40分): 1≤n,m≤5×105 1\le n,m\le 5\times 10^5 。