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

Input

题意翻译

给出一个序列$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 提供的翻译

加入题单

上一题 下一题 算法标签: