迷之逆序
Time Limit: 1000 ms
Memory Limit: 65536 KiB
Problem Description
MLE 得到了 QAQ 的真传,但 QAQ 为了检验 MLE 智商是否可以真正领悟,于是出了这一道题:给出 n 个数的序列,先把每个数逆序(如 120 变为 21,123 变为 321),将会产生 n 个新数,我们把它称作序列 A。
之后对序列 A 中的 n-1 个数进行 q 次操作,每次操作将会把序列 A 上的某个数替换成另一个数,并询问序列 A 中任取连续的一段数,如何取才能使这段数的和最大,请你输出最大值。
Input
输入数据有多组(数据组数不超过 100)。
对于每组数据:
- 第一行输入 n, q (1 <= n <= 10000, 1 <= q <= 100) 分别表示数字个数和操作次数
- 接下来的一行输入 n 个正整数,最大不超过 10000
- 接下来的 q 行,每行输入 2 个整数,分别为要替换的数的位置 xi (1 <= xi <= n) 和要修改的值 yi (-10000 <= yi <= 10000)
当 n = 0 时输入结束。
Output
对于每组数据第一行输出 "Case #x:" (不包括引号,冒号后无空格),x 表示当前为第几组数据。之后对应 q 次操作每次操作输出一行,表示查询的答案。
Sample Input
5 2 1 2 3 4 5 2 -5 2 5 3 3 45 12 32 3 -5 1 5 2 10 0
Sample Output
Case #1: 12 18 Case #2: 75 26 15
Hint
请大家仔细核对 "Case #x:",建议复制样例输出的模式以防输出时不符合题目要求而导致的 Wrong Answer。
Source
【2016级《程序设计基础(B)II》期末上机考试-第一场】MLE_kenan