본문 바로가기

세그먼트 트리

(4)
[BOJ] 16910 mex와 쿼리 [문제 링크](https://www.acmicpc.net/problem/16910) 문제 요약 다음과 같은 세 쿼리를 처리해야 합니다. [l,r]에 속하는 모든 자연수를 배열 A에 추가한다. 이미 있는 수는 무시된다. [l,r]에 속하는 모든 자연수를 배열 A에서 제거한다. 없는 수는 무시된다. [l,r]에 속하는 모든 자연수에 대해 있으면 제거, 없으면 추가한다. 각 쿼리를 수행 한 뒤에 이 배열에 없는 수 중 가장 작은 자연수를 찾으면 됩니다. 문제 풀이 일단 문제에서 요구하는 좌표가 크니 좌표 압축을 시도하고 생각합시다. 그 이후 Lazy Propagation 달려 있는 세그로 연산을 처리해주며 특정 구간에 존재하는 수의 개수를 세 주면 됩니다. Lazy 연산 중에 1번 쿼리와 2번 쿼리는 서로 상..
[BOJ] 13309 트리 문제 링크: https://www.acmicpc.net/problem/13309 13309번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부모 정점을 나타내는 정수 a가 주어진다 (1 ≤ a ≤ N). 다음 Q개의 줄 각각에는 세 정수 b, c, d가 주어진다. d = 0이면, b와 c를 연결하는 경로가 존재하는 지 묻는 질의만 수행함을 의미한다. d = 1이면, b와 c를 연 www.acmicpc.net 문제 요약: 정점이 20만개인 트리가 주어진다. 이때 어떤 정점 a, b를 잇는 경로가 있는 지에 대한 쿼리 20만개에 응답..
[BOJ] 15977 조화로운 행렬 2018 KOI 고등부 3번이다. 정해는 2d segment tree래서 그렇게 짰는데 사실 set+이분탐색이 훨씬 짧고 깔끔하고 빠르고 메모리 사용량도 적다고 한다. 하여튼 "정해"는 첫째 열 기준으로 정렬한 다음 둘째 열과 셋째 열에서 2d segment tree를 이용해서 pair의 LIS를 구해주면 된다. 메모리 사용량이 문제고 $200000 * (lg200000)^2$ 개만큼 노드 잡았더니 MLE 뜨길래 적당히 줄여서 해봤더니 맞았다. 왜 맞는지 진짜 모르겠는데 실제로 돌리면 같은 노드도 여러번 탐색하고 그래서 최악의 경우에도 노드 개수가 많이 넘어가지는 않는다고 한다. 시간은 5초 제한에 낭낭하게 3.7초 나왔다. (...) 시간복잡도는 $O(n lg n^2)$, 공간복잡도도 마찬가지.다시는 ..
[BOJ] 2472 체인점 굉장한 학생 문제랑 다익스트라의 짬뽕이다. 덕분에 코드가 장난아니게 길다.각 정점이 최대 5개의 간선을 가지니 다익스트라의 $O(ElgV)$ 시간복잡도가 $O(VlgV)$로 바뀐다. 그러면 주어진 세 정점에 대해서 다익스트라를 한번씩 돌려볼 수 있고, 모든 정점에 대해 주어진 세 정점으로부터 각 정점으로부터의 거리 $dist_i$가 나오게 된다. 거리의 범위는 크지만 대소관계만을 비교하면 되므로 등위를 정렬을 통해 다시 매겨주자. 그러면 굉장한 학생 문제처럼 모든 정점에 대해 체인점을 세울수 있음/없음을 판별할 수 있다. 그 이후 들어오는 쿼리는 $O(1)$에 처리 가능하다. 수행 시간은 다익스트라, 정렬, RMQ 등이 다 섞여서 결과적으로 $O(NlgN)$이다. 개인적으로 문제 자체도 굉장한 학생 문제..