发布时间: 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 个数 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 题解：对于区间更新的题目，第一时间就想到用线段树做。由于要保存历史最大值和历史最小值，因此更新瞬时最小值，瞬时最大值以及懒惰标记时需要注意。更新懒惰标记add1时，如果c>0且add1<0时，要先把标记往下更新。因为add1本可以使区间内的数变小，然而加上正数c后，这些数会“变得不那么小”，从而无法记录历史最小值，因此需要先把懒惰标记往下更新，再加上c。（更新add2时同理）
#include<bits/stdc++.h> #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; const int MX = 1e5 + 5; /****** sum1:瞬时最小值 sum2:瞬时最大值 Min:历史最小值 Max:历史最大值 add1:对于sum1的懒惰标记 add2:对于sum2的懒惰标记 ******/ int sum1[MX<<2],sum2[MX<<2],Min[MX<<2],Max[MX<<2],add1[MX<<2],add2[MX<<2]; void PushUP(int rt){ sum1[rt]=min(sum1[rt<<1],sum1[rt<<1|1]); sum2[rt]=max(sum2[rt<<1],sum2[rt<<1|1]); Min[rt]=min(Min[rt],sum1[rt]); Max[rt]=max(Max[rt],sum2[rt]); } void build(int l,int r,int rt){ add1[rt]=add2[rt]=0; if(l==r){ int x; scanf("%d",&x); Min[rt]=Max[rt]=sum1[rt]=sum2[rt]=x; return; } int m=(l+r)>>1; build(lson); build(rson); PushUP(rt); } /****** 更新懒惰标记add1时，如果c>0且add1<0时，要先把标记往下更新。 因为add1本可以使区间内的数变小，然而加上正数c后，这些数会“变得不那么小”， 从而无法记录历史最小值，因此需要先把懒惰标记往下更新，再加上c ******/ void down1(int c,int l,int r,int rt){ sum1[rt]+=c; Min[rt]=min(sum1[rt],Min[rt]); if(l==r) return; int m=(l+r)>>1; if(c>0&&add1[rt]<0){ down1(add1[rt],lson); down1(add1[rt],rson); add1[rt]=c; } else add1[rt]+=c; } void down2(int c,int l,int r,int rt){ sum2[rt]+=c; Max[rt]=max(sum2[rt],Max[rt]); if(l==r) return; int m=(l+r)>>1; if(c<0&&add2[rt]>0){ down2(add2[rt],lson); down2(add2[rt],rson); add2[rt]=c; } else add2[rt]+=c; } void PushDown(int l,int r,int rt){ int m=(l+r)>>1; if(add1[rt]){ down1(add1[rt],lson); down1(add1[rt],rson); add1[rt]=0; } if(add2[rt]){ down2(add2[rt],lson); down2(add2[rt],rson); add2[rt]=0; } } void update(int L,int R,int c,int l,int r,int rt){ if(L<=l&&R>=r){ down1(c,l,r,rt); down2(c,l,r,rt); return; } int m=(l+r)>>1; PushDown(l,r,rt); if(L<=m) update(L,R,c,lson); if(R>m) update(L,R,c,rson); PushUP(rt); } int query(int p,int l,int r,int rt){ if(l==r) return max(abs(Max[rt]),abs(Min[rt])); int m=(l+r)>>1; PushDown(l,r,rt); int ret; if(p<=m) ret=query(p,lson); else ret=query(p,rson); PushUP(rt); return ret; } int main(){ int T,n,m; //freopen("in.txt","r",stdin); scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); build(1,n,1); int op,a,b,x; while(m--){ scanf("%d",&op); if(op==1){ scanf("%d%d%d",&a,&b,&x); if(a>b) swap(a,b); update(a,b,x,1,n,1); } else{ scanf("%d",&x); printf("%d\n",query(x,1,n,1)); } } } return 0; }
