CodeForces - 935F Fafa and Array —— 线段树

本文主要是介绍CodeForces - 935F Fafa and Array —— 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Fafa has an array A of n positive integers, the function f(A) is defined as$\sum _{i=1}^{n-1}|a_i-a_{i+1}|$. He wants to do q queries of two types:

1 l r x — 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.
2 l r x — increase all the elements in the range [l,  r] by value x.
Note that queries of type 1 don’t affect the array elements.

Input
The first line contains one integer n (3 ≤ n ≤ 105) — the length of the array.

The second line contains n positive integers a1, a2, …, an (0 < ai ≤ 109) — the array elements.

The third line contains an integer q (1 ≤ q ≤ 105) — the number of queries.

Then q lines follow, line i describes the i-th query and contains four integers ti li ri xi .

It is guaranteed that at least one of the queries is of type 1.

Output
For each query of type 1, print the answer to the query.

Examples
Input
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
Output
2
8
Input
5
1 2 3 4 5
4
1 2 4 2
2 2 4 1
2 3 4 1
1 2 4 2
Output
6
10

题意：

给你n个数，对于f(a)的定义见题目，给你两个操作，1 l r x 代表你可以在l到r之间选一个数加上x，让f(a)最大，或者可以不加，2 l r x 代表在l到r之间的所有数都加上x。

题解：

对于第一个操作，我们可以知道，如果$a_{i-1}-a_i$>0的时候，增加ai会减小f(a)，在$a_i-a_{i+1}$<0的时候，增加ai会减小f(a),那么我们只要维护当$a_{i-1}-a_i$>0,$a_i-a_{i+1}$<0的时候的和，之后若是小于x，那么就是ans+2*(x-sum).第二个操作，改变的只是l,l-1,r,r+1范围的值，稍微修改一下即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
ll a[N],de[N],sum[N<<2];
void update(int l,int r,int root,int pos)
{if(l==r){ll ans=0;if(de[pos-1]>0)ans+=de[pos-1];if(de[pos]<0)ans-=de[pos];sum[root]=ans;return ;}int mid=l+r>>1;if(mid>=pos)update(l,mid,root<<1,pos);elseupdate(mid+1,r,root<<1|1,pos);sum[root]=min(sum[root<<1],sum[root<<1|1]);
}
ll query(int l,int r,int root,int ql,int qr)
{if(l>=ql&&r<=qr)return sum[root];int mid=l+r>>1;ll ans=1e17;if(mid>=ql)ans=query(l,mid,root<<1,ql,qr);if(mid<qr)ans=min(ans,query(mid+1,r,root<<1|1,ql,qr));return ans;
}
int main()
{int n,m;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);ll all=0;for(int i=1;i<n;i++){de[i]=a[i]-a[i+1];all+=abs(de[i]);if(i>1)update(1,n,1,i);}int op,l,r;ll x;scanf("%d",&m);while(m--){scanf("%d%d%d%lld",&op,&l,&r,&x);if(op==1){if(l==r)printf("%lld\n",all-abs(de[l-1])-abs(de[l])+abs(de[l-1]-x)+abs(de[l]+x));else{ll ans=query(1,n,1,l,r);if(ans>x)printf("%lld\n",all);elseprintf("%lld\n",all+2*(x-ans));}}else{all-=(abs(de[l-1])+abs(de[r]));de[l-1]-=x,de[r]+=x;all+=(abs(de[l-1])+abs(de[r]));update(1,n,1,l),update(1,n,1,r);if(l-1>1)update(1,n,1,l-1);if(r+1<n)update(1,n,1,r+1);}}return 0;
}

这篇关于CodeForces - 935F Fafa and Array —— 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---