센터가 돋보여야 해 (JUNGOL 6122)

https://jungol.co.kr/problem/6122

---

아이디어

세그먼트 트리를 만들어줄것입니다. 이때 트리의 각 노드가 저장하는 구간의 다음과 같은 값들을 저장해줄 것입니다.

 

$Max$ - 구간 내의 최댓값

$Min$ - 구간 내의 최솟값

$MaxMin$ - 구간 내의 $l,r (l<r)$을 잡아서 $A_l-A_r$의 최댓값

$MinMax$ - 구간 내의 $l,r (l<r)$을 잡아서 $-A_l+A_r$의 최댓값

$MinMaxMin$ - 구간 내의 $a,b,c (a<b<c)$를 잡아서 $-A_a+A_b-A_c$의 최댓값

 

이때 두 구간을 합치는것은 $O(1)$에 수행할 수 있으므로 이를 세그먼트 트리에 넣어주면 됩니다.

---

아이디어

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

struct Range{
    ll Max=-1e17,Min=1e17,MaxMin=-1e17,MinMax=-1e17,MinMaxMin=-1e17;
};

Range tree[1515151];
Range Blank;

Range operator+(Range A,Range B)
{
    Range res;

    res.Max=max(A.Max,B.Max);
    res.Min=min(A.Min,B.Min);
    res.MaxMin=max({A.MaxMin,B.MaxMin,A.Max-B.Min});
    res.MinMax=max({A.MinMax,B.MinMax,-A.Min+B.Max});
    res.MinMaxMin=max({A.MinMaxMin,A.MinMax-B.Min,-A.Min+B.MaxMin,B.MinMaxMin});

    return res;
}

void update(ll s,ll e,ll node,ll idx,ll num)
{
    if (idx<s || e<idx) return;
    if (s==e)
    {
        tree[node].Max=tree[node].Min=num;
        tree[node].MaxMin=tree[node].MinMax=tree[node].MinMaxMin=-1e17;
        return;
    }
    ll mid=(s+e)/2;
    update(s,mid,node*2,idx,num);
    update(mid+1,e,node*2+1,idx,num);
    tree[node]=tree[node*2]+tree[node*2+1];
}
Range solve(ll s,ll e,ll node,ll l,ll r)
{
    if (e<l || r<s) return Range();
    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,i,Q,a,b,c;

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

    for (i=0;i<Q;i++)
    {
        cin>>a>>b>>c;
        if (a==1) update(1,N,1,b,c);
        else cout<<solve(1,N,1,b,c).MinMaxMin<<"\n";
    }
}