Karin的弹幕
题目描述
Karin在战斗之余的闲暇时光里喜欢上B站看鬼畜视频，尤其喜欢发弹幕。她这天对一个视频的弹幕产生了兴趣，她记录了每个时间点的弹幕数量，并且可能对一段呈等差数列的时间的弹幕数量求最大值；她还可能修改某个时间点的弹幕数量。
为了不在Yuuna面前暴露出她弱爆了的数学能力，保持她傲娇的属性，你需要帮助她。
精简题意：给定一个序列，支持以下操作：①对一段下标是等差数列的子序列进行求最大值操作(参见输入格式)；②单点修改。
输入格式
第一行是一个整数n，
第二行是一个长度为n的整数序列a1...an，
第三行是一个整数m，
接下来m行，每行首先有一个整数op，
然后，若op=0，则之后有两个整数p，v，代表将a[p]的值加上v，
若op=1，则之后有两个整数x0，d，代表询问max{a[x0],a[x0+d],a[x0+2d],...,a[x0+kd]}(x0+kd<=n,x0+(k+1)d>n)。
数据中可能有多余空格。
输出格式
对每个op=1，单独输出一行，代表该等差子序列的最大值。
【输入样例1】
10
1 6 1 4 9 4 8 2 8 5
10
1 3 3
0 5 4
0 3 8
1 2 5
1 4 8
1 7 5
1 3 6
0 1 2
1 5 3
1 4 9
【输入样例2】
10
-9 -6 2 -10 -2 -6 10 6 -4 -2
10
1 2 3
1 6 3
0 7 8
0 4 -6
0 10 -5
1 10 4
0 3 -8
1 2 4
0 10 -5
1 1 2
【输出样例1】
8
8
4
8
9
13
4
【输出样例2】
6
-4
-7
-6
18
数据范围与约定
【数据范围】
1<=n<=70000，
1<=m<=70000，
保证任何时刻abs(a[i])(1<=i<=n)<=2147483647，
0<=op<=1，
1<=p<=n，
abs(v)<=2147483647
1<=x0<=n,
1<=d<=n，
保证涉及的所有数在C++的int内。
2015.4.2新加四组数据