알고리즘 공부방

2D Segment Tree는 y축에 Segment Tree 한개, x축에 Segment Tree 한개를 이용하여 이차원 좌표상의 한 점 업데이트 및 구간 연산 쿼리를 빠르게 처리할 수 있는 자료구조이다. y축 Segment Tree는 각 노드마다 x축 Segment Tree 를 하나씩 갖고 있으며, 정확히는 구간 [yl, yr]을 담당하고 있을 때, 각 노드가 [yl, yr][x, x] 를 노드로 갖는 x축 Segment Tree 를 의미한다. 그냥 구현하면 공간 복잡도가 $O(N^2)$ 이니, Dynamic Segment Tree로 X축, Y축을 모두 구현할 필요가 있다. Dynamic Segment Tree를 사용하다 보니, Pointer 을 사용한 구현과 벡터 기반의 구현 두가지가 모두 존재한다...

머지 소트 트리란, 말 그대로 머지 소트의 과정을 그대로 저장하여 만들어논 트리이다. 예를 들어 최대 부분합 문제를 분할정복으로 푼 후, 그 과정을 세그먼트 트리로 옮겨 놓을 수 있듯이, 머지 소트가 일어나는 과정을 각각 하나의 노드로 만들어 저장하는 것이다. #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int MAXN = 1e5; int N, Q, A[MAXN+10]; vector tree[4*MAXN+10]; void combine(vector &a, vector &b, vector &c) { int pa=0, pb=0; while(pa

https://contests.ioi-jp.org/open-2018/index.htmlhttps://oj.uz/problems/source/351 역시 JOIOC는 어렵다. 문제 하나하나가 다 좋은 문제이고, 많이 생각할 수 있게 해주는 문제들인 것 같다.4일동안 1, 4번을 풀었고, 2번은 부분점수, 3번은 풀지 못하였다.Heavy Light Decomposition을 응용한 DP 최적화, Sqrt Decomposition 등 아직 내가 익숙하지 않은 개념들이 많이 이용되어서 더 어렵게 느껴진 것 같다. 나중에 이런 개념들을 잘 익힌 후에 꼭 다시 풀어봐야 할 문제들이다. 4. xylophone 순열이 하나 있고, 물어볼 수 있는 쿼리는 오직 어떤 구간 내의 최대값-최솟값만 물어볼 수 있을 때 2N 번..

문제 https://oj.uz/problem/view/JOI14_scarecrows 문제 보기 - 허수아비 (JOI14_scarecrows) :: oj.uz JOI 마을에 있는 넓은 황무지에는 $N$명의 신성한 허수아비가 서 있어, 주민들은 일 년에 몇 번씩 허수아비를 둘러싸고 축제를 하고 있었습니다. JOI 마을의 촌장은 "허수아비들의 말씀을 들었다"고 주장하며 황무지에 밭을 하나 만들 계획을 세웠습니다. 허수아비들의 말에 따르면 밭은 다음 조건을 충족해야 한다고 합니다. 각 변이 동서 방향 또는 남북 방향으로 놓인 직사각형이어야 합니다. 남서쪽의 꼭짓점과 북동쪽의 꼭짓점에는 허수아비가 서 있어야 합니다. oj.uz 평면 상에 N개의 점들이 주어져 있을때 다음 조건을 만족하는 점들의 순서쌍의 수를 세는..

문제 https://www.acmicpc.net/problem/7626 직사각형 여러개가 주어졌을 때, 그 합집합의 넓이를 구하는 문제이다. 풀이 이 문제에 대한 풀이는 https://codedoc.tistory.com/421 에 매우 자세히 나와 있다. 직사각형들의 x좌표에 대해 직사각형의 왼쪽 변은 +1, 오른쪽 변은 -1을 해주는 이벤트로 생각할 수 있다. 따라서 그러한 이벤트들을 모두 x좌표에 대해 정리한 후 오른쪽으로 쭉 한번 훑어주면서 넓이를 구할 수 있다. 이제 잘 나눈 x좌표들에 대한 구간으로 그 구간 사이의 넓이만 구해주면 된다. x좌표들에 대한 이벤트로 정렬을 때린 후 구간을 나눴으니, 하나의 구간 내에선 구해야 하는 영역의 넓이는 변하지 않는다. 따라서 이벤트들을 잘 관리해주는 자료구..

문제 https://www.acmicpc.net/problem/1395 스위치 n개에 대하여 특정 구간의 스위치를 모두 반전시키거나, 구간에 있는 켜져 있는 스위치의 수를 세는 쿼리를 해결하는 문제이다. 풀이 세그먼트 트리를 이용한다. 세그먼트 트리의 각 노드가 해당 구간의 켜져 있는 스위치들의 수를 갖고 있다면, 2번째 쿼리는 쉽게 해결할 수 있다. 문제는 첫번째 쿼리가 하나의 스위치를 반전시키는 것이 아니라, 특정 구간의 모든 스위치들을 반전시키는 것이다. 따라서 세그먼트 트리 레이지 프로파게이션을 사용해야 한다. 레이지 배열에는 그 구간에 대한 반전 연산이 적용되었는가 여부를 저장한다. 구간합에 대한 레이지처럼 구간 업데이트를 할 때 자신이 완전히 속한 노드에 대해서, 레이지값을 자식들에게 넘겨주며..

기본적인 세그먼트 트리는 구간에 대한 쿼리와, 특정 값을 업데이트하는 연산밖에 안된다. 만약 구간에 대해 업데이트 하는 연산이 필요하다면 Lazy Propagation 을 사용해야 한다. 간단한 원리는 업데이트해야하는 구간에 완전히 속한 노드들에게 lazy 값을 올려준 후, 나중에 그 노드를 방문할 때가 됬을때 lazy 값을 꺼내서 실제 값에 업데이트 해주는 방식이다. *더 구체적인 설명은 https://www.acmicpc.net/blog/view/26을 참고한다. struct SEG { int n; vector tree, lazy; SEG() {} SEG(int n) : n(n), tree(n*4+10), lazy(n*4+10) { init(1, 1, n); } void init(int node, i..

엄청나게 중요한 자료구조인 세그먼트 트리에 대하여 알아보고 가자. 세그먼트 트리의 목적은 구간에 대한 질의와 수정을 빠르게 하는 것이다. 아이디어는 다음과 같다. 구간 트리의 루트는 배열의 전체 구간인 [1, n]을 표현하며, 그 왼쪽 노드는 [1, mid], 오른쪽 노드는 [mid+1, n]을 포함하게 함으로서 재귀적으로 구간에 대한 정보를 이진 트리에 저장한다. 만약 구간에 대한 쿼리가 떨어진다면 그 쿼리의 구간에 해당하는 노드들을 몇개 잡아 그 그 부분에 대해서만 계산하면 된다. 세그먼트 트리 자체의 원리에 대한 자세한 내용은 다른 블로그나 종만북을 복습하도록 하고, 구현과 시간복잡도에 초점을 맞춰 보자. *세그먼트 트리의 이론 및 구현 : https://www.acmicpc.net/blog/vie..