#156. 你能回答这些问题吗

你能回答这些问题吗

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定长度为 N\red N 的数列 A\red A,以及M条指令,每条指令可能是以下两种之一:

1\red 1、“1 x y”,查询区间 [x,y]\red{[x,y]} 中的最大连续子段和,即 maxxlry\red{maxx\le l\le r\le y} i=lrA[i]\red{{\sum i=lrA[i]}}

2\red 2、“2 x y”,把 A[x]\red{A[x]} 改成 y\red y

对于每个查询指令,输出一个整数表示答案。

输入格式

第一行两个整数 N\red N , M\red M

第二行 N\red N 个整数 A[i]\red{A[i]}

接下来 M\red M 行每行 3\red 3 个整数 k\red k , x\red x , y\red yk=1\red{k=1} 表示查询(此时如果 x>y\red{x>y},请交换 x,y\red{x,y}),k=2\red{k=2}表示修改。

输出格式

对于每个查询指令输出一个整数表示答案。

每个答案占一行。

样例

输入样例

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

输出样例

2
-1

提示

N500000\red{N\le 500000},

M100000\red{M\le 100000}

周日下午班

未参加
状态
已结束
规则
IOI
题目
6
开始于
2022-10-9 6:00
结束于
2022-10-17 14:00
持续时间
200 小时
主持人
参赛人数
10