BOJ 31234 - 대역폭 관리

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

경인지역 대학연합 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 쪽을 조금 더 집중하게 되지 않을까 싶습니다.

Read more

말이 샐러드가 되어가 / なみぐる

얘는 그냥 장르폭이 넓음... 보카코레 출품곡인 즌다몬머시기들로 접했었는데 다양하게 잘 만드시는거같아요 M/V 영상 Lyrics 가사 また頭の中身がまとまらなくて 마타 아타마노 나카미가 마토마라나쿠테 또다시 머릿속이 정리되지 않아서 言葉がサラダになっていく 코토바가 사라다니 낫테이쿠 말이 샐러드가 되어가 出力された無意味の羅列で 슈츠료쿠사레타 무이미노 라레츠데 출력되어지는 무의미한 나열으로 視界が緑になっていく 시카이가 미도리니 낫테이쿠 시야가 초록색이 되어가 とりとめのない孤独な言葉が 토리토메노 나이 코도쿠나

By 박성훈
14898 서로 다른 수와 쿼리 2의 MST 풀이

14898 서로 다른 수와 쿼리 2의 MST 풀이

[l,r] 구간에서 서로 다른 수의 갯수를 세는 쿼리는 보통 offline 하게 mo's algorithm 등을 사용하여 해결하는데, online한 쿼리를 강제하는 문제에서는 보통 persistant segment tree를 깔끔한 정해로 보는 것 같습니다. 입력값을 조금 처리하는 것으로, merge sort tree를 통해서 이러한 쿼리를 처리할 수 있기 때문에, 이에 대해서 짚어보도록 하겠습니다.

By 박성훈

당신밖에 보이지 않아 / r-906

r-906의 따끈따끈한 신곡 간간히 나오는 사진이라던지 중간의 멜로디파트 등을 통해서 Catchy?! 의 후속곡임을 쉽게 알아볼 수 있습니다 M/V 영상 Lyrics 가사 きっと運命の寵児 킷토 운메이노 초우지 분명 운명에게 사랑받아 まるで魔性の物語(ストーリー) 마루데 마쇼우노 스토리 마치 마성과 같은 스토리 誰もが釘付けの一等星 다레모가 쿠기즈케노 잇토우세이 모두가 점찍어둔1 일등성 でもね 데모네 그치만 あなたも知らないあなたを 아나타모

By 박성훈

boj 24915 센터가 돋보여야 해

금광세그와 boj 16993최근 ett/hld도 그렇고, 구간에 대해서 다루는 쿼리에 대해서 좀 깊게 공부해보고 있다. 일반적인 부분합 세그먼트 트리와는 다른 형태의 문제들을 해결해보고 있기에, 발상을 좀 정리해보고자 한다. 세그먼트 트리와 구간 세그먼트 트리의 주요 조건 및 세그트리가 주로 필요한 장소는 * 구간에 대한 쿼리를 진행하면서 * 각 쿼리당 처리시간이 빨라야 하고 * 인접한

By 박성훈