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

你简化了这个问题，将问题分为两种查询：

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

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

传送门：SHUOJ422

Input

第一行有一个整数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

Output

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

Sample Input

1
2
3
4
5
6
7
8
9
1
5 6
1 -1 2 3 -3
1 1 5 1
2 1
2 2
1 2 4 -5
2 2
2 3

Sample Output

1
2
3
4
2
1
5
3

题解

线段树求历史最值 有三个域 一个是当前总的变化值 另外两个是历史变化最大值和最小值 注意pushdown时更新的顺序应该是先用父亲的变化最大最小值和孩子当前总的变化值来更新孩子的变化最大最小值，然后再更新孩子总的变化值 注意pushdown后的清空 因为是单点查询 这三个域可以全是lazy标记
## AC code:(不包含输入类) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.io.*;  
import java.util.*;  
public class Main {  
    static int[]shu;  
    public static void main(String[] args) {  
        FastScanner sc = new FastScanner();  
        PrintWriter pw = new PrintWriter(System.out);  
        int c=sc.nextInt();  
        while (sc.hasNext()) {  
            int n=sc.nextInt();  
            int m=sc.nextInt();  
            shu=new int[n+1];  
            SegTree tree=new SegTree(n+1);  
            for(int i=1;i<=n;i++){  
                shu[i]=sc.nextInt();  
            }  
            for(int i=0;i<m;i++){  
                int t=sc.nextInt();  
                if(t==1){  
                    int l=sc.nextInt();  
                    int r=sc.nextInt();  
                    int add=sc.nextInt();  
                    tree.regupdate(l, r+1, add);  
                }else{  
                    int index=sc.nextInt();  
                    pw.println(tree.regquery(index, index+1,shu));  
                }  
            }  
            pw.flush();  
        }  
    }  
}  
class Node{  
    long shu;  
    long lazy;  
    long maxchange;  
    long minchange;  
    Node(long num,long lazy){  
        this.shu=num;  
        this.lazy=lazy;  
        this.maxchange=0;  
        this.minchange=0;  
    }  
}  
class SegTree{  
    //Node[]tree=new Node[400050];  
    long[]lazy=new long[400050];  
    long[]maxchange=new long[400050];  
    long[]minchange=new long[400050];  
    int n;  
    SegTree(int n_){  
        this.n=1;  
        while(n<n_){  
            n*=2;  
        }  
        //for(int i=0;i<400050;i++)tree[i]=new Node(0,0);  
    }  
    void pushdown(int num,int l,int r){  
        //if(lazy[num]!=0){  
            maxchange[num*2+1]=Math.max(maxchange[num]+lazy[num*2+1], maxchange[num*2+1]);  
            minchange[num*2+1]=Math.min(minchange[num]+lazy[num*2+1], minchange[num*2+1]);  
            maxchange[num*2+2]=Math.max(maxchange[num]+lazy[num*2+2], maxchange[num*2+2]);  
            minchange[num*2+2]=Math.min(minchange[num]+lazy[num*2+2], minchange[num*2+2]);  
            //tree[num*2+1].shu+=tree[num].lazy;  
            //tree[num*2+2].shu+=tree[num].lazy;  
            lazy[num*2+1]+=lazy[num];  
            lazy[num*2+2]+=lazy[num];  
            lazy[num]=0;  
            maxchange[num]=0;  
            minchange[num]=0;  
        //}  
    }  
    void update(int num,int l,int r,long add,int x,int y){  
        if(r<=x||l>=y)return;  
        if(l<=x&&r>=y){  
            //tree[num].shu+=add;  
            lazy[num]+=add;  
            maxchange[num]=Math.max(maxchange[num], lazy[num]);  
            minchange[num]=Math.min(minchange[num], lazy[num]);  
            return;  
        }  
        pushdown(num,x,y);  
        update(num*2+1,l,r,add,x,(x+y)/2);  
        update(num*2+2,l,r,add,(x+y)/2,y);  
        //tree[num].shu=tree[num*2+1].shu+tree[num*2+2].shu;    
    }  
    void regupdate(int l,int r,int add){  
         update(0,l,r,add,0,n);  
    }  
    long regquery(int l,int r,int[]shu){  
        return query(0,l,r,0,n,shu);  
    }  
    long query(int num,int l,int r,int x,int y,int[]shu){  
        if(r<=x||l>=y)return 0;  
        if(l<=x&&r>=y){  
            return Math.max(Math.abs(shu[l]+maxchange[num]), Math.abs(shu[l]+minchange[num]));  
        }  
        pushdown(num,x,y);  
        long left=query(num*2+1,l,r,x,(x+y)/2,shu);  
        long right=query(num*2+2,l,r,(x+y)/2,y,shu);  
        if(left!=0)  
            return left;  
        else  
            return right;  
    }  
}