小Y正在观测y地区的风力情况，他在一条直线上依此设定了 n 个观测点，并观测与直线垂直方向的风力值，风力有时是正向的也有时是反向的，规定正向时的风力值为正数，他发现每次风力值的变化都可以表示为观测点上一条线段 [L,R] 上的同时增强或者减弱。小Y希望能够实时统计这些观测点的数据，并且实时分析这些观测点在历史中到达的风力最大绝对值，但是他无法同时对大量的观测点进行分析, 更重要的是他记不住这些观测点过去的风力大小，于是他希望你来用计算机帮助他完成这个任务。
你简化了这个问题，将问题分为两种查询：
1.对观测点 [L,R] 上的风力正向增强 X 。（ X 为负数表示正向减弱，即反向加强）
2.查询观测点 A 上的历史风力最大绝对值。
输入第一行有一个整数 T 表示数据组数。（ T<=10 ） 接着有 T 组数据，每组数据第一行是整数 n 和 q ，表示观测点个数和查询次数。 第二行有 n 个数 a1,...,an ，表示每个观测点的风力初始值。 接着有 q 行，表示 q 次操作，格式为： 1 L R X：表示对 [L，R] 线段上的正向风力同时增强 x 。 2 A：表示查询 A 点的历史风力最大绝对值。 1<=n,q<=100000 。 1<=L,R,A<=n −10000<=ai , X<=10000
输出对每次询问2，输出一个数字表示风力值并换行。
样例输入1 1 5 6 1 -1 2 3 -3 1 1 5 1 2 1 2 2 1 2 4 -5 2 2 2 3 样例输出1 2 1 5 3这道题和普通线段树的区间询问区别在于当延迟标记累加时，标记会覆盖，无法更新出来子节点的历史最大值。
举个栗子： 总区间为【1,2】
首先对 区间 【1,2】+2 ，
再对区间【1,2】-1， 现在记录【1,2】的节点延迟标记会变成 1 。
接着询问节点1的历史最大值时，答案很明显是2，但是延迟下沿的时候只会更新+1.所以很明显问题在于标记无法覆盖。那我们怎么处理呢。
其实我们只需要记录延迟标记累加时出现的最大值和最小值，cur，max和minn这三个变量就可以完成。
记录对于每个节点延迟标记累加时出现的最大值和最小值，因为单点询问，所以标记最终会更新到最下面的节点上，
延伸：这道题只是单点询问，而如果改成询问区间历史最大值这样写就不行了。
武汉网络赛e起来编程 25.Events，区间修改，但是武汉这道更加复杂，需要区间询问历史最大值
参考 25. Events （e起来编程”（武汉网络赛）） 线段树（区间修改，区间查询）
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <stack> #include <map> #include <set> #include <vector> #include <queue> #define mem(p,k) memset(p,k,sizeof(p)); #define rep(a,b,c) for(int a=b;a<c;a++) #define pb push_back #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define inf 0x6fffffff #define ll long long using namespace std; const int maxn=100010; int maxx[maxn<<2],minn[maxn<<2]; int cur[maxn<<2]; int n,q,l,r,x; void build(int l,int r,int rt){ if(l==r){ scanf("%d",maxx+rt); cur[rt]=minn[rt]=maxx[rt]; return; } cur[rt]=minn[rt]=maxx[rt]=0; int m=(l+r)>>1; build(lson); build(rson); } void pushdown(int rt){ if(cur[rt] || maxx[rt] ||minn[rt]){ maxx[rt<<1]=max(maxx[rt<<1],cur[rt<<1]+maxx[rt]); minn[rt<<1]=min(minn[rt<<1],cur[rt<<1]+minn[rt]); maxx[rt<<1|1]=max(maxx[rt<<1|1],cur[rt<<1|1]+maxx[rt]); minn[rt<<1|1]=min(minn[rt<<1|1],cur[rt<<1|1]+minn[rt]); cur[rt<<1]+=cur[rt]; cur[rt<<1|1]+=cur[rt]; minn[rt]=maxx[rt]=cur[rt]=0; } } void update(int L,int R,int x,int l,int r,int rt){ if(L<=l && r<=R){ cur[rt]+=x; maxx[rt]=max(maxx[rt],cur[rt]); minn[rt]=min(minn[rt],cur[rt]); return; } int m=(l+r)>>1; pushdown(rt); if(m>=L)update(L,R,x,lson); if(m<R)update(L,R,x,rson); } int query(int k,int l,int r,int rt){ if(l==r){ return max(abs(maxx[rt]),abs(minn[rt])); } pushdown(rt); int m=(l+r)>>1; if(m>=k)return query(k,lson); else return query(k,rson); } int main() { int t; cin>>t; while(t--){ scanf("%d%d",&n,&q); build(1,n,1); while(q--){ scanf("%d",&x); if(x==1){ scanf("%d%d%d",&l,&r,&x); update(l,r,x,1,n,1); } else{ scanf("%d",&x); cout<<query(x,1,n,1)<<endl; } } } return 0; } /* */
