304927: CF935F. Fafa and Array
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Fafa and Array
题意翻译
给出一个序列$A$ ,定义函数$f(A)=\sum_{i=1}^{n-1}|a_i-a_{i+1}|$ 给出两种操作: $1.l$ $r$ $x$ ,在区间$[l,r]$ 内找一个位置,使得把这个位置的值加上$x$ 后,$f(A)$ 最大,求这个最大值 $2.l$ $r$ $x$ ,把区间$[l,r]$ 加上$x$ $n\le10^5,q\le10^5,x_i\le10^9$ 感谢@Kelin 提供的翻译题目描述
Fafa has an array $ A $ of $ n $ positive integers, the function $ f(A) $ is defined as ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF935F/dc9a0a0772798ba9fb8b149f527b509b8571b93b.png). He wants to do $ q $ queries of two types: - $ 1lrx $ — find the maximum possible value of $ f(A) $ , if $ x $ is to be added to one element in the range $ [l,r] $ . You can choose to which element to add $ x $ . - $ 2lrx $ — increase all the elements in the range $ [l,r] $ by value $ x $ . Note that queries of type $ 1 $ don't affect the array elements.输入输出格式
输入格式
The first line contains one integer $ n $ $ (3<=n<=10^{5}) $ — the length of the array. The second line contains $ n $ positive integers $ a_{1},a_{2},...,a_{n} $ $ (0<a_{i}<=10^{9}) $ — the array elements. The third line contains an integer $ q $ $ (1<=q<=10^{5}) $ — the number of queries. Then $ q $ lines follow, line $ i $ describes the $ i $ -th query and contains four integers $ t_{i}l_{i}r_{i}x_{i} $ ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF935F/b4776844d7d2421177af411bd5745433670f68b1.png). It is guaranteed that at least one of the queries is of type $ 1 $ .
输出格式
For each query of type $ 1 $ , print the answer to the query.
输入输出样例
输入样例 #1
5
1 1 1 1 1
5
1 2 4 1
2 2 3 1
2 4 4 2
2 3 4 1
1 3 3 2
输出样例 #1
2
8
输入样例 #2
5
1 2 3 4 5
4
1 2 4 2
2 2 4 1
2 3 4 1
1 2 4 2
输出样例 #2
6
10