这是本蒟蒻有史以来做的第二道线段树的题,竟然调了3天。在%%%wangyi%%%的帮助下终于于2017年4月27日19时10分AC。感谢上帝感谢主感谢社会感谢党感谢人民感谢毛主席。。。。

题意:其实这就是一道区间最大最小求和线段树。给定一个矩阵,最多有20行,106次方个元素。有3种操作:

1 x1 y1 x2 y2 c : 把(x1,y1),(x2,y2)间的元素加上c(c>0,x1<x2,y10,x1<x2,y1<y2)

3 x1 y1 x2 y2 : 把(x1,y1),(x2,y2)间的总和、最小值、最大值。

思路:由于行数很小,所以对每一行建树,暴力更新每一行。对于每个树节点,保存最大、最小、和。

以下是代码的注释

upshdown(标记下传):有set操作先下传并将子节点的add清空,再下传add。(就是这样)

upgrade(即updata):更新最大、最小、和。

所以就是这么简单的题,坑了我3天。