알고리즘 공부방

https://apio2019.ru/https://oj.uz/problems/source/389https://koosaga.com/232 내가 참가한 첫번째 apio 대회이다. 대회 결과는... 30점으로 매우 참혹한 점수가 나왔다.나는 대회시간에 device 를 읽고 어려운 수학문제라 판단하여 기본적인 부분점수만 긁고 풀지 않았는데, 이것이 가장 쉬운 문제였다. 대신 나는 마지막 문제였던 lamps에 모든 시간을 쏟아부었고, 결국 완벽한 풀이를 찾은 후 2D segment tree 구현, 경로압축까지 구현을 끝냈는데 MLE가 나서 결국 이것도 섭태밖에 긁지 못했다. 나중에 다시 풀어보니 경로압축 없이 fenwick + dynamic segment tree 하나만 있어도 AC가 나왔다...이번 년도의 문..

https://koosaga.com/121 https://codeforces.com/gym/100551/problem/A https://www.acmicpc.net/problem/16911 cp-algorithms.com/data_structures/deleting_in_log_n.html 1. 간선 추가 2. 간선 삭제 3. 정점 u, v가 연결되어 있는지 판별 이 문제를 online 으로 처리하는 것은 매우 어려운 문제이다. 따라서 Offline 으로 분할정복을 활용하여 해결하자. 가장 먼저, 각 간선의 생존시간을 시간축에 표시하면 어떠한 구간이 된다. 이 구간을 segment tree에 $logN$ 개의 노드에 업데이트 된 것이라고 생각하고, 이후 segment tree의 노드들을 전위순회하면서 u..