본문 바로가기

segment_tree

BOJ 18798 - OR과 쿼리 (D5) 사용 알고리즘 풀이 1 : Fenwick Tree + Segment Tree (binary search) + Offline Query + fastIO (O(30NlogN)) 풀이 2 : Fenwick Tree + Segment Tree (bitwise AND) (O(30N + NlogN)) 풀이 1 이 풀이의 기본 아이디어는 KOI'23 고기 파티 문제 풀이를 기반으로 한다. 모든 수들은 1번 쿼리에 의해서 어떤 시점에서 K가 되었다가 다시 K가 아니게 된다. OR 연산이 단조성을 띄므로 이 K가 되는 구간은 연속하게 된다. 그래서 모든 수에 대해서 이 시점을 기록한 후, 이를 나중에 쭉 처리하는 아이디어를 이용한다. 1번 쿼리에 순서대로 번호를 붙이자. 이제 i=1~n에 대하여 Ai가 언제 K가 되는.. 더보기
BOJ 25392 - 사건의 지평선 (D3) 사용 알고리즘 Segment Tree + SCC + 위상정렬 dp 풀이 일단 어떻게 했는진 몰라도 i->L~R 간선을 잘 이어줬다고 치자. 무한 번 표시된다 = 사이클에서 돌고 있다는 의미이다. 따라서 사이클 내부에서 가장 큰 원소를 찾으면 그 사이클 내부에서의 정답이 된다. 단 어떤 사이클 u에서 v로 간선이 있는경우, u에서의 정답은 max(u 내부에서의 정답, v 내부에서의 정답)이다. 따라서 위상정렬 dp로 순차적으로 사이클에서의 최댓값을 결정해나가면 된다. 이제 i->L~R 간선을 깔끔하게 처리하는 법만 생각하면 된다. L~R은 구간이다. 구간 크기가 O(N)이므로 간선이 최대 O(N^2)개가 생긴다. 그렇다면 구간을 O(logN) 정도로 표현할 수 있다면 추가해야 하는 간선은 O(NlogN)개.. 더보기
BOJ 29202 - 책가방 (D5) 2023 KSA Automata G번이다. 아레나 당시에 27점까지 긁었는데, 27점 풀이로 44점까지 긁을 수 있었다는 걸 대회 때 알았으면 더 좋았을 것 같다. 사용 알고리즘 Segment Tree + 좌표 압축 && 그리디 (우선순위 큐) 풀이 일단 섭태3을 풀어보자. 부피의 최댓값만 고려하면 되므로 부피 기준으로 오름차순으로 정렬하고 정렬된 배열에서 x번 책을 고르면, 1~x-1 사이 책은 모두 부피가 \( V_{x} \) 이하이다. 따라서 이 중에서 무게가 작은 k-1개를 골라주는게 이득이다. 이는 우선순위 큐(max heap)의 크기를 k-1으로 유지하고, 하나의 변수를 관리하는 것으로 해결할 수 있다. for(int i = 0 ; i < n ; i++)v[i].i=i+1; sort(all(v.. 더보기
BOJ 10070 - 벽 (D5) 사용 알고리즘 segment tree + lazy propagation 풀이 뭔가 쉬워보이긴 한데 해보면 바로 해결되지는 않는 그런 문제이다. 세그먼트 트리의 각 노드는 그 노드가 담당하는 구간의 수 범위를 저장한다. 이제 얘를 어떻게 업데이트하고 전파할지가 문제이다. 업데이트할 노드의 원래 수 범위가 [L,R]이고 업데이트할 값이 X라 하자. 일단 이 노드가 업데이트할 구간에 완전히 포함되는 경우를 보자. op = 1의 경우는 L = max(L,X), R = max(R,X)로 하면 된다. 마찬가지로 op = 2는 L = min(L,X), R = min(R,X)로 하면 된다. 업데이트할 구간에 걸치면, 자식 노드들을 봐야하는데 이때 원래 자식 노드들의 [L,R]과 현재 노드의 [L,R]을 비교해서 자식 .. 더보기

티스토리툴바