题目名称 3240. Can you answer these queries III
输入输出 GSS_3.in/out
难度等级 ★★★☆
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试数据 10
题目来源 GravatarLGLJ 于2019-09-16加入
开放分组 全部用户
提交状态
分类标签
线段树 树状数组
分享题解
通过:26, 提交:59, 通过率:44.07%
GravatarLGLJ 100 0.548 s 45.87 MiB C++
Gravatar┭┮﹏┭┮ 100 0.797 s 48.08 MiB C++
Gravatar锝镆氪锂铽 100 0.808 s 45.87 MiB C++
Gravatarsyzhaoss 100 0.876 s 49.08 MiB C++
Gravatarop_组撒头屯 100 1.225 s 45.87 MiB C++
Gravatarcb 100 1.260 s 45.87 MiB C++
Gravatar. 100 1.277 s 46.08 MiB C++
Gravataryrtiop 100 1.331 s 42.97 MiB C++
Gravatar梦那边的美好ET 100 1.429 s 52.08 MiB C++
Gravatarflyfree 100 1.615 s 30.76 MiB C++
关于 Can you answer these queries III 的近10条评论(全部评论)
线段树进阶amazing!!
Gravatar┭┮﹏┭┮
2023-09-08 20:42 4楼
Gravataryrtiop
2021-07-03 13:14 3楼
150小水关过!!
Gravatar乐未殇
2019-12-06 21:18 2楼
同[cogs 775]山海经
GravatarLGLJ
2019-09-16 19:20 1楼

3240. Can you answer these queries III

★★★☆   输入文件:GSS_3.in   输出文件:GSS_3.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

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

1、1 x y,查询区间 $[x,y]$ 中的最大连续子段和,即$ \max\limits_ {x\le l \le r\le y} {\sum\limits_{i=l}^r A_i}$

2、2 x y,把 $A[x]$ 改成 $y$。

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

【输入格式】

第一行两个整数$N,M$。

第二行$N$个整数$A[i]$。

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

【输出格式】

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

每个答案占一行。

【样例输入】

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

【样例输出

2
-1

【提示】

$N≤500000,M≤100000, -1000\leq A[i]\leq 1000$

【来源】

《算法竞赛进阶指南》