风力观测

发布时间: 2017年7月9日 18:17   最后更新: 2017年7月9日 21:04   时间限制: 1000ms   内存限制: 128M

小Y正在观测y地区的风力情况,他在一条直线上依此设定了$n$个观测点,并观测与直线垂直方向的风力值,风力有时是正向的也有时是反向的,规定正向时的风力值为正数,他发现每次风力值的变化都可以表示为观测点上一条线段$[L, R]$上的同时增强或者减弱。小Y希望能够实时统计这些观测点的数据,并且实时分析这些观测点在历史中到达的风力最大绝对值,但是他无法同时对大量的观测点进行分析, 更重要的是他记不住这些观测点过去的风力大小,于是他希望你来用计算机帮助他完成这个任务。

你简化了这个问题,将问题分为两种查询:

1.对观测点$[L,R]$上的风力正向增强$X$。($X$为负数表示正向减弱,即反向加强)

2.查询观测点$A$上的历史风力最大绝对值。

第一行有一个整数$T$表示数据组数。($T<=10$)
接着有$T$组数据,每组数据第一行是整数$n$和$q$,表示观测点个数和查询次数。
第二行有$n$个数$a_1,...,a_n$,表示每个观测点的风力初始值。
接着有$q$行,表示$q$次操作,格式为:
1 L R X:表示对$[L,R]$线段上的正向风力同时增强$x$。
2 A:表示查询$A$点的历史风力最大绝对值。
$1<=n,q<=100000$。
$1<=L,R,A<=n$
$-10000<=a_i$, $X<=10000$

对每次询问2,输出一个数字表示风力值并换行。

复制
1
5 6
1 -1 2 3 -3
1 1 5 1
2 1
2 2
1 2 4 -5
2 2
2 3
2
1
5
3

2017

“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛