체육 수행평가 (JUNGOL 3900)

https://jungol.co.kr/problem/3900?cursor=NTA4LDAsNw==

---

아이디어

세그먼트 트리를 만들어서 특정 구간 내의 모든 고깔을 방문했을 때의 이동거리와 한개를 제외하고 방문했을 때의 최소 이동거리를 저장합시다. 이때 인접한 두 구간을 합칠 때 모든 고깔을 방문하는 경우는 그냥 (왼쪽 구간의 모든 고깔 방문)+(두 구간 사이 점의 거리)+(오른쪽 구간의 모든 고깔 방문)을 해주면  되며, 하나를 제외하고 방문하는 경우는 추가로 왼쪽 구간의 맨 오른쪽 고깔을 지나지 않는 경우와 오른쪽 구간의 맨 왼쪽 고깔을 지나지 않는 경우를 고려해주면 됩니다.

---

소스코드

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

struct Tree{
    ll s,e,Dis0,Dis1;
};

vector <pair <ll,ll> > Loc;

ll GetDis(ll idx1,ll idx2)
{
    return abs(Loc[idx1].first-Loc[idx2].first)+abs(Loc[idx1].second-Loc[idx2].second);
}

Tree operator +(Tree A,Tree B)
{
    Tree res;
    res.s=A.s;
    res.e=B.e;
    res.Dis0=A.Dis0+B.Dis0+GetDis(A.e,B.s);

    res.Dis1=min(A.Dis1+GetDis(A.e,B.s)+B.Dis0,A.Dis0+GetDis(A.e,B.s)+B.Dis1);
    if (A.s!=A.e) //한칸짜리가 아니면
        res.Dis1=min(res.Dis1,A.Dis0-GetDis(A.e-1,A.e)+GetDis(A.e-1,B.s)+B.Dis0); //A의 맨 오른쪽 빼기
    if (B.s!=B.e)
        res.Dis1=min(res.Dis1,A.Dis0+B.Dis0-GetDis(B.s,B.s+1)+GetDis(A.e,B.s+1)); //B의 맨 왼쪽 제거
    
    return res;
}

Tree tree[404040];
Tree init(ll s,ll e,ll node)
{
    if (s==e)
    {
        tree[node].s=s;
        tree[node].e=e;
        tree[node].Dis0=0;
        tree[node].Dis1=2e9;
        return tree[node];
    }

    ll mid=(s+e)/2;
    return tree[node]=init(s,mid,node*2)+init(mid+1,e,node*2+1);
}
void update(ll s,ll e,ll node,ll idx,ll x,ll y)
{
    if (idx<s || e<idx) return;
    if (s==e)
    {
        Loc[idx]={x,y};
        return;
    }
    ll mid=(s+e)/2;
    update(s,mid,node*2,idx,x,y);
    update(mid+1,e,node*2+1,idx,x,y);
    tree[node]=tree[node*2]+tree[node*2+1];
}
Tree solve(ll s,ll e,ll node,ll l,ll r)
{
    if (l<=s && e<=r) return tree[node];
    ll mid=(s+e)/2;

    if (r<=mid) return solve(s,mid,node*2,l,r);
    if (mid+1<=l) return solve(mid+1,e,node*2+1,l,r);
    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,i,a,b,c;
    char type;

    cin>>N>>Q;
    Loc.resize(N+1);
    for (i=1;i<=N;i++)
        cin>>Loc[i].first>>Loc[i].second;
    init(1,N,1);

    for (i=0;i<Q;i++)
    {
        cin>>type;
        if (type=='Q')
        {
            cin>>a>>b;
            Tree res=solve(1,N,1,a,b);

            cout<<min(res.Dis0,res.Dis1)<<"\n";
        }
        else
        {
            cin>>a>>b>>c;
            update(1,N,1,a,b,c);
        }
    }
}