BOJ 31234 - 대역폭 관리
재미있는 문제여서 가져와봤습니다. 경인지역 대학연합 SHAKE 2023 문제인데, 이 대회를 칠 당시에는 hld를 안배웠어서 접근을 못했었던 문제였습니다.
![BOJ 31234 - 대역폭 관리](/content/images/size/w1200/2024/07/------.png)
서론
재미있는 문제여서 가져와봤습니다.
경인지역 대학연합 SHAKE 2023 문제인데, 이 대회를 칠 당시에는 hld를 안배웠어서 접근을 못했었던 문제였습니다.
![](https://blog.koder.page/content/images/2024/07/image-31.png)
그래도 나름 선방하기는 했었던 아레나였는데, 아마 이 문제를 시간내에 풀었더라면 퍼포 SSS를 띄웠을 것 같아요
![](https://blog.koder.page/content/images/2024/07/image-28.png)
발상
한계 대역폭을 어떻게 처리하느냐가 핵심 아이디어인데, 구간 최댓값을 관리하는 lazy segment tree을 작성하고, 초기에 한계 대역폭 값을 음수로 걸어주면 문제를 해결할 수 있습니다.
지문에서 들어오는 쿼리로
![](https://blog.koder.page/content/images/2024/07/image-29.png)
대역폭 증가 업데이트 쿼리를 처리하고 난 뒤에, 최댓값 쿼리를 날려봅니다.
최댓값 쿼리가 0을 초과하면 원래 걸어두었던 한계 대역폭을 초과한 대역폭이 지나가고 있는 것이기 때문에 break 후 결과를 출력해주면 됩니다.
트리에서 구간쿼리를 처리하기 때문에, heavy-light decomposition을 활용해서 트리를 쪼개서 관리해주면 문제를 해결할 수 있다.
![](https://blog.koder.page/content/images/2024/07/image-30.png)
태그 목록이 살벌한 문제.
개인적으로 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
를 달성했습니다.
![](https://blog.koder.page/content/images/2024/07/image-32.png)
개강 이전에 다이아V를 달성하는것을 목표로 삼았었는데, 대학입시나 대학교에서의 활동 등으로 치여사느라 기회가 없었다만 이번 방학을 통해 찍어둘 수 있었어서 다행이라는 생각이 듭니다.
티어를 더 이상 올리는 것보다는 제가 취약한 부분에 대한 보강이나 codeforces 쪽을 조금 더 집중하게 되지 않을까 싶습니다.