1406D - Three Sequences - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T, class U>
// T -> node, U->update.
struct Lsegtree{
    vector<T>st;
    vector<U>lazy;
    ll n;
    T identity_element;
    U identity_update;
    Lsegtree(ll n, T identity_element, U identity_update)
    {
        this->n = n;
        this->identity_element = identity_element;
        this->identity_update = identity_update;
        st.assign(4*n,identity_element);
        lazy.assign(4*n, identity_update);
    }
    T combine(T l, T r)
    {
        // change this function as required.
        T ans = (l + r);
        return ans;
    }
    void buildUtil(ll v, ll tl, ll tr, vector<T>&a)
    {
        if(tl == tr)
        {
            st[v] = a[tl];
            return;
        }
        ll tm = (tl + tr)>>1;
        buildUtil(2*v + 1, tl, tm,a);
        buildUtil(2*v + 2,tm+1,tr,a);
        st[v] = combine(st[2*v + 1], st[2*v + 2]);
    }
    // change the following 2 functions, and you're more or less done.
    T apply(T curr, U upd, ll tl, ll tr)
    {
        T ans = curr+(tr-tl+1)*upd;
        return ans;
    }
    U combineUpdate(U old_upd, U new_upd, ll tl, ll tr)
    {
        U ans = old_upd;
        ans=old_upd+new_upd;
        return ans;
    }  
    void push_down(ll v, ll tl, ll tr)
    {
        if(lazy[v] == identity_update)return;
        st[v] = apply(st[v], lazy[v], tl, tr);
        if(2*v + 2 < 4*n)
        {
            ll tm = (tl + tr)>>1;
            lazy[2*v + 1] = combineUpdate(lazy[2*v+1], lazy[v], tl, tm);
            lazy[2*v + 2] = combineUpdate(lazy[2*v+2], lazy[v], tm+1,tr);            
        }
        lazy[v] = identity_update;
    }
    T queryUtil(ll v, ll tl, ll tr, ll l, ll r)
    {
        push_down(v,tl,tr);
        if(l > r)return identity_element;
        if(tr < l or tl > r)
        {
            return identity_element;
        }
        if(l <= tl and r >= tr)
        {
            return st[v];
        }
        ll tm = (tl + tr)>>1;
        return combine(queryUtil(2*v+1,tl,tm,l,r), queryUtil(2*v+2,tm+1,tr,l,r));
    }
 
    void updateUtil(ll v, ll tl, ll tr, ll l, ll r, U upd)
    {
        push_down(v,tl,tr); 
        if(tr < l or tl > r)return;
        if(tl >=l and tr <=r)
        {
            lazy[v] = combineUpdate(lazy[v],upd,tl,tr);
            push_down(v,tl,tr);
        }
        else
        {
            ll tm = (tl + tr)>>1;
            updateUtil(2*v+1,tl,tm,l,r,upd);
            updateUtil(2*v+2,tm+1,tr,l,r,upd);
            st[v] = combine(st[2*v + 1], st[2*v+2]);
        }
    }



    void build(vector<T>a)
    {
        assert(a.size() == n);
        buildUtil(0,0,n-1,a);
    }
    T query(ll l, ll r)
    {
        return queryUtil(0,0,n-1,l,r);
    }
    void update(ll l,ll r, U upd)
    {
        updateUtil(0,0,n-1,l,r,upd);
    }
};

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
ll n;
cin>>n;
ll totinc=0;
vector<ll>arr(n);
for(ll i=0;i<n;i++){
	cin>>arr[i];
	if(i>0&&arr[i]>arr[i-1]){
		totinc+=arr[i]-arr[i-1];
	}
}
Lsegtree<ll,ll>st(n,0,0);
st.build(arr);
ll po=arr[0]-totinc;
ll df=0;
if(abs(po)%2!=0){
	po--;
	df++;

}
po/=2;
cout<<po+totinc+df<<"\n";
ll q;
cin>>q;
while(q--){
	ll l,r,x;
	cin>>l>>r>>x;
    l--;
    r--;
   
    if(l>0){
    	ll pre,cn;
      if(st.query(l,l)>st.query(l-1,l-1)){
      	  pre=st.query(l,l)-st.query(l-1,l-1);
      	 
      }
      else{
      	pre=0;
      }
      if(st.query(l,l)+x>st.query(l-1,l-1)){
      	cn=st.query(l,l)+x-st.query(l-1,l-1);
      }
      else{
      	cn=0;
      }
      totinc+=cn-pre;

    }
    if(r<n-1){
       ll pre,cn;
      if(st.query(r+1,r+1)>st.query(r,r)){
      	  pre=st.query(r+1,r+1)-st.query(r,r);
      	 
      }
      else{
      	pre=0;
      }
      if(st.query(r+1,r+1)>st.query(r,r)+x){
      	cn=st.query(r+1,r+1)-st.query(r,r)-x;
      }
      else{
      	cn=0;
      }
      totinc+=cn-pre;
    }
    st.update(l,r,x);
    po=st.query(0,0)-totinc;
    df=0;
if(abs(po)%2!=0){
	po--;
	df++;

}
po/=2;
cout<<po+totinc+df<<"\n";


}








 



return 0;
 
	 

}