#CS1190. 子数组和查询

子数组和查询

题目背景

翻译自 CSES-1190 题。

题目描述

给定一个包含 n 个整数的数组。数组中的一些值将被更新，每次更新后，您的任务是报告数组中的最大子数组和。

本题中子数组定义为：任意给定一个数组下标 l,r(1≤l≤r≤n)l,r(1\le l\le r\le n)l,r(1≤l≤r≤n)，得到的区间 [l,r][l,r][l,r] 中的数组元素 al,al+1,⋯ ,ara_{l},a_{l+1},\cdots,a_ral​,al+1​,⋯,ar​。即可以理解成连续子序列。

输入格式

第一行包含两个整数 n 和 m：分别表示数组的大小和更新的次数。数组的索引从 1 到 n。

第二行包含 n 个整数 x1,x2,…,xnx_1,x_2,…,x_nx1​,x2​,…,xn​：表示数组的初始内容。

接下来有 m 行描述更新操作。每一行包含两个整数 k 和 x：表示将数组中位置 k 的值更新为 x。

输出格式

对于每次更新操作，输出更新后的数组的最大子数组和。空子数组（和为 0）是允许的。

样例

5 3
1 2 -3 5 -1
2 6
3 1
2 -2

9
13
6

说明/提示

$1 \leq n,m \leq 2 \cdot 10^5,-10^9 \leq x_i \leq 10^9,-10^9 \leq x \leq 10^9,1 \leq k \leq n$