河蟹王国

河蟹王国

测试数据来自 system/1659

描述

河蟹王国有一位河蟹国王,他的名字叫羊驼。河蟹王国富饶安定,人们和谐相处。有一天,羊驼国王心血来潮,想在一部分人中挑出最和谐的人。于是,羊驼国王将他的子民排成了一列(==!!b汗~好长呀)。每个人都有一个初始的和谐值。羊驼国王每次会选择一个区间[L,R],这个区间中和谐值最大的人就是国王选出的人。而且,在某一时间,区间[L',R']里的人会变得熟悉,因此他们每个人的和谐值都会上升一个相同的值C。羊驼国王想知道,对于每一次选择,他选出的最大和谐值是多少。

格式

输入格式

第一行是一个数N(1<=N<=100000),表示人数。

接下来的N行,每行一个数,表示排成的序列第i个人和谐值的初始值。

接下来是一个数M(1<=M<=100000),表示羊驼国王或他的子民有所活动(羊驼国王选择一个区间算一次,某区间里的人增长和谐值算一次)的总次数。

接下来的M行,每行第一个是一个数K,K是1或2,若K=1,接下来有三个数L,R,C,表示区间[L,R]的所有人增加C的和谐值;若K=2,接下来有两个数L,R,表示国王选择了区间[L,R]。

输出格式

每次对于国王选择区间,输出选择区间里的最大和谐值。

样例1

样例输入1

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

样例输出1

4
6

限制

每个测试点1s。

提示

保证所有的数以及结果都在longint范围内。

来源

经典问题改编。

信息

ID
1556
难度
(无)
分类
数据结构 | 线段树 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者