| 题目名称 | 3240. Can you answer these queries III |
|---|---|
| 输入输出 | GSS_3.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 LGLJ
于2019-09-16加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：25， 提交：51， 通过率：49.02% | ||||
 LGLJ |
100 | 0.548 s | 45.87 MiB | C++ |
 ┭┮﹏┭┮ |
100 | 0.797 s | 48.08 MiB | C++ |
|
锝镆氪锂铽 |
100 | 0.808 s | 45.87 MiB | C++ |
|
syzhaoss |
100 | 0.876 s | 49.08 MiB | C++ |
|
op_组撒头屯 |
100 | 1.225 s | 45.87 MiB | C++ |
 cb |
100 | 1.260 s | 45.87 MiB | C++ |
 . |
100 | 1.277 s | 46.08 MiB | C++ |
|
yrtiop |
100 | 1.331 s | 42.97 MiB | C++ |
|
梦那边的美好ET |
100 | 1.429 s | 52.08 MiB | C++ |
 乐未殇 |
100 | 1.642 s | 93.34 MiB | C++ |
| 关于 Can you answer these queries III 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
线段树进阶amazing!!
| ||||
|
| ||||
|
150小水关过！！
乐未殇
2019-12-06 21:18
2楼
| ||||
|
同[cogs 775]山海经
LGLJ
2019-09-16 19:20
1楼
| ||||
【题目描述】
给定长度为$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$
【来源】
《算法竞赛进阶指南》