#T2133. 子数组和查询(Subarray Sum Queries)

子数组和查询(Subarray Sum Queries)

链接: https://cses.fi/problemset/task/1190

板块: Range Queries

时限: 1.00 s | 内存: 512 MB

题目描述

有一个由 nn 个整数组成的数组。数组中的某些值会被更新,每次更新后,你的任务是报告数组中最大的子数组和。

输入

第一行输入包含整数 nn 和 mm:分别表示数组大小和更新次数。数组下标为 1,2,…,n1,2,\ldots,n。

下一行包含 nn 个整数 x1,x2,…,xnx_1,x_2,\ldots,x_n:数组的初始内容。

随后有 mm 行描述修改操作。每行包含两个整数 kk 和 xx:位置 kk 上的值变为 xx。

输出

每次更新后,输出最大子数组和。允许使用空子数组(其和为 00)。

数据范围

1≤n,m≤2⋅1051 \le n, m \le 2 \cdot 10^5 −109≤xi≤109-10^9 \le x_i \le 10^9 1≤k≤n1 \le k \le n −109≤x≤109-10^9 \le x \le 10^9

样例输入

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

样例输出

9
13
6