[codeforces]round670 D. Three Sequences

#include<bits/stdc++.h>
#define debug(x) cout<<#x<<" is "<<x<<endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define DBG 0
const int N = 1e5 + 5;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LLINF = (1LL<<60);
using namespace std;
typedef pair<int,int> pii;
ll n,q;
ll a[N];
ll differ[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
#if DBG
	freopen("input.txt","r",stdin);
#endif
	cin>>n;
	ll tot  = 0;
	
	for(int i = 1;i <= n;i++){
		cin>>a[i];
		differ[i] = a[i] - a[i - 1];
		if(differ[i] > 0 && i != 1)tot += differ[i];
	}
	ll k = (differ[1] - tot) / 2;
	cout<<max(differ[1] - k,tot + k)<<endl;
	cin>>q;
	while(q--){
		ll l,r,x;
		cin>>l>>r>>x;
		if(l == 1)differ[1] += x;
		else {
			if(x < 0){
				if(differ[l] > 0)tot -= min(differ[l],-x);
			}else{
				if(differ[l] + x >= 0)tot += min(differ[l] + x,x);
			}
			differ[l] += x;
		}
		if(r + 1 <= n){
			if(x > 0){
				if(differ[r + 1] > 0)tot -= min(differ[r + 1],x);
			}else{
				if(differ[r + 1] - x >= 0)tot += min(differ[r + 1] - x,-x);
			}
			differ[r + 1] -= x;
		}
		k = (differ[1] - tot) / 2;
		cout<<max(differ[1] - k,tot + k)<<endl;
	}
	return 0;
}

本文地址：https://blog.csdn.net/qq_20252251/article/details/108558104