구사과

http://acm.hdu.edu.cn/showproblem.php?pid=5306 세 종류의 쿼리를 지원하는 자료구조를 설계하는 문제이다. O((N + Q)lgN)에 해야 한다. * 1. 구간 [L, R]에 a[i] = min(a[i], V) 대입 * 2. 구간 최댓값 * 3. 구간 합 보통 이러한 문제들은 세그먼트 트리에 익숙하면 쉽게 풀 수 있고, 실제로 2번 쿼리까지는 쉬운 문제지만, 이 문제는 3번 쿼리 때문에 굉장히 어려운 문제가 되었다.해법을 이해하기까지도 상당히 힘들었는데, 결론부터 말하자면 다음 네 값을 관리해줘야 한다 : 구간 합, 구간 최댓값, 구간에서 최댓값이 자신의 값인 원소의 수, 구간 두번째 최댓값. 두번째 최댓값은 최댓값보다 작아야만 한다. 먼저 이 값들을 제대로 관리했다면,..

그래프 이론에서 Dynamic Connectivity Problem은, * 1. 정점 u, v를 잇는 간선 추가 * 2. 정점 u, v를 잇는 간선 제거 (이미 있다고 치자.) * 3. 그래프 상에서 두 정점이 연결되어 있는지 체크와 같은 질의가 주어졌을 때, 이러한 질의를 빠르게 응답하는 방법을 찾는 문제이다. O(Q|V|) 나 O(Q|E|) 정도에는, 기본적인 그래프 탐색 알고리즘으로도 아주 쉽게 풀수 있지만, 더 나은 복잡도를 내기는 쉽지 않은 문제이다. 2번 쿼리가 없다면 union-find data structure (링크) 를 사용해서 쉽게 풀 수 있지만, 더 복잡한 질의가 들어왔을 때는 쉬운 풀이가 존재치 않는다. 일반적인 경우 이 문제의 해법은 매우 어려워 보인다 (링크). 하지만, 오프라..

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=639&page=show_problem&problem=4917 설명이 개판인 점은 양해 부탁한다 (풀이 쓸 시간이 없음.. ㅠㅠ) 어떠한 시간에 대해서 겹치는 구간이 100개인데, 이는 임의의 interval i 에 대해서, sj < si이며 자신과 교차하는 interval이 100개 이하라는 것으로 해석할 수 있고, 고로 모든 교차 쌍의 개수가 100N개 이하라는 결론으로 귀결된다. 요트를 모두 시작점 순으로 정렬하자. 만약에 요트가 단 하나라면, 간단한 dynamic programming을 통해서 O(N)에 해결할 수 있다. 문제는 요트가 두개라는 ..