[Ynoi2013] D2T2
题目描述
给一个长为 $n$ 的序列,有 $m$ 次查询操作。
查询操作形如 $l\;r\;L\;R$,表示将序列中值在 $[L,R]$ 内的位置保留不变,其他的位置变成 $0$ 时,序列中 $[l,r]$ 区间内的最大子段和,这个子段可以是空的。
输入输出格式
输入格式
第一行两个整数 $n,m$。
第二行 $n$ 个整数表示这个序列。
之后 $m$ 行,每行四个整数 $l\;r\;L\;R$ 表示一次查询操作。
输出格式
输出 $m$ 行,每行一个整数表示答案。
输入输出样例
输入样例 #1
6 5
-1 1 -4 5 -1 4
1 1 4 5
1 1 4 514
2 3 3 3
1 6 -1 5
2 5 2 5
输出样例 #1
0
0
0
9
5
说明
Idea:nzhtl1477,Solution:ccz181078,Code:ccz181078,Data:nzhtl1477
对于 $100\%$ 的数据,$1\leq n,m \le 10^5$,序列中所有数的绝对值 $\le 10^9$。
第四组查询中,值域限制是 $[-1,5]$,序列为 `-1 1 0 5 -1 4`,区间 $[1,6]$ 的最大子段为 $[2,6]$,和为 $9$。
第五组查询中,值域限制是 $[2,5]$,序列为 `0 0 0 5 0 4`,区间 $[2,5]$ 的最大子段为 $[4,4]$(并列),和为 $5$。