왼손에는 콜라, 오른손에는 피자 (JUNGOL 8356)

https://jungol.co.kr/problem/8356?cursor=MTIsMSw2

---

아이디어

세그먼트 트리를 구조체로 만들어봅시다. 각 구간에서 콜라의 최댓값, 치킨의 최댓값, 그 구간에서 두개를 고를때의 최댓값을 저장해봅시다. 그리고 왼쪽과 오른쪽을 병합할 때 그 값들을 갱신시켜주면 됩니다. 그러면 O(log N)에 변경과 최댓값 구하기 쿼리를 다 처리할 수 있습니다.

---

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

struct Tree{
    ll ColaMax=-1e18,ChickenMax=-1e18,Ans=-1e18;
};
Tree operator+(Tree A,Tree B)
{
    Tree res;
    res.ColaMax=max(A.ColaMax,B.ColaMax);
    res.ChickenMax=max(A.ChickenMax,B.ChickenMax);
    res.Ans=max({A.Ans,B.Ans,A.ColaMax+B.ChickenMax});
    return res;
}

Tree tree[404040];
void update(ll s,ll e,ll node,ll type,ll idx,ll num)
{
    if (idx<s || e<idx) return;
    if (s==e)
    {
        if (type==1) tree[node].ColaMax=num;
        if (type==2) tree[node].ChickenMax=num;
        return;
    }
    ll mid=(s+e)/2;
    update(s,mid,node*2,type,idx,num);
    update(mid+1,e,node*2+1,type,idx,num);
    tree[node]=tree[node*2]+tree[node*2+1];
}
Tree solve(ll s,ll e,ll node,ll l,ll r)
{
    if (e<l || r<s) return {(ll)-1e18,(ll)-1e18,(ll)-1e18};
    if (l<=s && e<=r) return tree[node];
    ll mid=(s+e)/2;
    return solve(s,mid,node*2,l,r)+solve(mid+1,e,node*2+1,l,r);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,Q,type,a,b,i;

    cin>>N;
    for (i=1;i<=N;i++)
    {
        cin>>a;
        update(1,N,1,1,i,a);
    }
    for (i=1;i<=N;i++)
    {
        cin>>a;
        update(1,N,1,2,i,a);
    }

    cin>>Q;
    for (i=0;i<Q;i++)
    {
        cin>>type>>a>>b;
        if (type<=2) update(1,N,1,type,a,b);
        if (type==3) cout<<solve(1,N,1,a,b).Ans<<"\n";
    }
}