서론

재미있는 문제여서 가져와봤습니다.

경인지역 대학연합 SHAKE 2023 문제인데, 이 대회를 칠 당시에는 hld를 안배웠어서 접근을 못했었던 문제였습니다.

그래도 나름 선방하기는 했었던 아레나였는데, 아마 이 문제를 시간내에 풀었더라면 퍼포 SSS를 띄웠을 것 같아요

발상

한계 대역폭을 어떻게 처리하느냐가 핵심 아이디어인데, 구간 최댓값을 관리하는 lazy segment tree을 작성하고, 초기에 한계 대역폭 값을 음수로 걸어주면 문제를 해결할 수 있습니다.

지문에서 들어오는 쿼리로

대역폭 증가 업데이트 쿼리를 처리하고 난 뒤에, 최댓값 쿼리를 날려봅니다.

최댓값 쿼리가 0을 초과하면 원래 걸어두었던 한계 대역폭을 초과한 대역폭이 지나가고 있는 것이기 때문에 break 후 결과를 출력해주면 됩니다.

트리에서 구간쿼리를 처리하기 때문에, heavy-light decomposition을 활용해서 트리를 쪼개서 관리해주면 문제를 해결할 수 있다.

태그 목록이 살벌한 문제.

개인적으로 lazy segment tree에서 구간 최댓값을 관리해본적이 없는 것 같은데, 이번 기회에 새로 시도해볼 수 있었어서 기억에 남는 문제입니다.

구현

void prop(int s, int e, int node){
    seg[node] += lazy[node];

    if(s != e){
        lazy[node*2] += lazy[node];
        lazy[node*2+1] += lazy[node];
    }
    lazy[node] = 0;
    return;
}

propagate 시키는 함수인데, 구간에 덧셈을 해주면 최댓값도 덩달아 더 커지니까 부분합 세그에서의 (e-s+1) 없이 바로 lazy[node] 를 더해주면 됩니다.

void seg_update(int l, int r, ll K, int s=1, int e=M, int node=1){
    if(lazy[node]) prop(s,e,node);
    if(r<s || e<l) return;
    if(l<=s && e<=r){
        lazy[node] = K;
        prop(s,e,node);
        return;
    }

    int mid = (s+e)/2;
    seg_update(l,r,K,s,mid,node*2);
    seg_update(l,r,K,mid+1,e,node*2+1);
    seg[node] = max(seg[node*2], seg[node*2+1]);
    return;
}

ll seg_query(int l, int r, int s=1, int e=M, int node=1){
    if(lazy[node]) prop(s,e,node);
    if(r<s || e<l) return MIN;
    if(l<=s && e<=r) return seg[node];

    int mid = (s+e)/2;
    return max(seg_query(l,r,s,mid,node*2), seg_query(l,r,mid+1,e,node*2+1));
}

세그는 propagate 시키는 부분이 포함된 것을 제외하면 일반적인 최댓값 세그트리와 동일합니다.

void hld(int now = 1){
    siz[now] = 1;
    for(int &nxt : g[now]){
        if(siz[nxt]) continue;

        dep[nxt] = dep[now] + 1;
        par[nxt] = now;

        hld(nxt);

        siz[now] += siz[nxt];
        if(siz[nxt] > siz[g[now][0]]) swap(nxt, g[now][0]);
    }
}

int idx = 0;
void ett(int now = 1){
    st[now] = ++idx;
    for(int nxt : g[now]){
        if(st[nxt]) continue;

        if(nxt == g[now][0]) chain[nxt] = chain[now];
        else chain[nxt] = nxt;
        ett(nxt);
    }
    ed[now] = idx;
}

오일러 투어 테크닉을 활용해서 트리를 구간 형태로 변화시키고, hld를 통해서 해당 구간들을 분할시킵니다.

ll hld_query(int s, int e){
    ll ret = MIN;
    while(chain[s] != chain[e]){
        if(dep[chain[s]] > dep[chain[e]]) swap(s,e);

        ret = max(ret, seg_query(st[chain[e]], st[e]));
        e = par[chain[e]];
    }

    if(st[s] > st[e]) swap(s,e);
    ret = max(ret, seg_query(st[s], st[e]));
    return ret;
}

void hld_update(int s, int e, ll K){
    while(chain[s] != chain[e]){
        if(dep[chain[s]] > dep[chain[e]]) swap(s,e);

        seg_update(st[chain[e]], st[e], K);
        e = par[chain[e]];
    }

    if(st[s] > st[e]) swap(s,e);
    seg_update(st[s], st[e], K);
}

hld_query 함수나 seg_query 에서 임의의 작은 숫자를 사용해야 함에 유의합니다. 저는 -2147483647을 사용했습니다.

    for(int i=1; i<=N; i++){
        cin >> a;
        seg_update(st[i],st[i],-a);
    }

초기에 대역폭 한계를 설정해 주는 부분입니다. -a 만큼을 update해주면 됩니다.

첨언

hld를 풀면서 boj 17429 국제 메시 기구 등의 문제를 쭉쭉 풀고, 오늘 solved.ac 기준 Diamond V를 달성했습니다.

개강 이전에 다이아V를 달성하는것을 목표로 삼았었는데, 대학입시나 대학교에서의 활동 등으로 치여사느라 기회가 없었다만 이번 방학을 통해 찍어둘 수 있었어서 다행이라는 생각이 듭니다.

티어를 더 이상 올리는 것보다는 제가 취약한 부분에 대한 보강이나 codeforces 쪽을 조금 더 집중하게 되지 않을까 싶습니다.