#O1100. 区间最大子段和

区间最大子段和

题目描述

给定长度为 nn 的序列 aa,维护 qq 次操作:

  • 1 p v:把 apa_p 修改为 vv;
  • 2 l r:询问 al,al+1,⋯ ,ara_l,a_{l+1},\cdots,a_r 的最大子段和(子段必须非空)。

输入格式

第一行两个整数 n,qn,q。

第二行 nn 个整数 aia_i。

接下来 qq 行,每行一个操作。

输出格式

对每个 2 操作输出一行一个整数,表示该区间的最大子段和。

样例 #1

样例输入 #1

5 3
-2 1 -3 4 -1
2 1 5
1 3 5
2 1 5

样例输出 #1

4
10

数据规模与约定

数据范围 说明
1≤n,q≤1051 \le n,q \le 10^5 序列长度与操作数
−1000≤ai,v≤1000-1000 \le a_i,v \le 1000 元素与修改值
  • 每个结点维护 sumsum、lmaxlmax、rmaxrmax、mxmx 四个量,合并时 mx=max⁡(lmxa,mxb,rmaxa+lmaxb)mx=\max(lmx_a,mx_b,rmax_a+lmax_b)。