정해는 Heavy Light trick인가 뭔가래고
그게 뭔지는 모르지만 나도 똑같은 풀이로 O(n lgn ^2)으로 풀었는데 보니까 세그 좌표압축으로 뚫리는거같더라
내가 그걸 해커컵에서 푼게 아니라 딴데서 풀어서 문제가 없는데 혹시 있으신분?
그게 뭔지는 모르지만 나도 똑같은 풀이로 O(n lgn ^2)으로 풀었는데 보니까 세그 좌표압축으로 뚫리는거같더라
내가 그걸 해커컵에서 푼게 아니라 딴데서 풀어서 문제가 없는데 혹시 있으신분?
핫하 죽어라
잭 정해가 hld라고??
그냥 세그트리로 뚫렸던거같은데
ㄴㄴ 디컴포지션이 아니라 작은걸 큰거에 합치는거였음
https://m.facebook.com/notes/facebook-hacker-cup/hacker-cup-2018-round-2-solutions/2286692684679953/
저 링크는 나랑 다르게 풀은것같네
나도 hld 안썼고 그냥세ㅡ그트리임
내가 처음 풀었을 땐 정해로 풀었음
그리고 HLD 문제 아님 ㅡㅡ
로그제곱에다가 이름이 헤비라이트길래 hld인줄 ㅋㅋ 저건또머여
나도 정확한 명칭은 모르겠는데 항상 작은걸 큰거에 합쳐줌으로서 모든 합치기 연산이 amortized O(n)에 됨
ㄴ쏘리 O(nlgn)
난 priority queue를 써서 구현을 좀 편하게 한 대신 amortized O(nlgn^2)에 했음