题目描述(ID:12323)
标题: 动态最大连续和
标签:
详情:
Zeratul有一个数列a[1...n],最开始数列中的所有元素都为负无穷大
接下来Zeratul要做m次操作,每次操作会把一个数改成一个非负整数。在每次操作之后,你要输出这个数列的最大连续和。所谓最大连续和,就是所有连续子序列a[L...R]的和的最大值。
输入格式:
第一行包括两个整数n,m,代表数列的长度和操作的次数。
接下来m行,每行包括两个整数pos,val,代表将a[pos]的值改为val。
输出格式:
输出m行,在每次操作之后输出这个数列的最大连续和。
限制: 对于30%的数据,n,m<=100。
对于50%的数据,n,m<=1000。
对于70%的数据,所有的pos不会重复,即每次操作前a[pos]的值都为负无穷大。
对于100%的数据,n,m<=100000,0<=val<=100000,1<=pos<=n
样例:

输入

5 5
1 5
2 4
3 3
5 100
4 5

输出

5
9
12
100
117

解释

第一次操作之后,数列为5 -INF -INF -INF -INF,最大连续和是5;
第二次操作之后,数列为5 4 -INF -INF -INF,最大连续和是9;
第三次操作之后,数列为5 4 3 -INF -INF,最大连续和是12;
第四次操作之后,数列为5 4 3 -INF 100,最大连续和是100;
第五次操作之后,数列为5 4 3 5 100,最大连续和是117。
登录并解答