Approach 자기보다 아래에 있는 트리에 물이 채워지면 현재 자신이 위치한 트리의 높이만큼의 물이 채워지는 방식이다. 따라서, 해당 위치에 얼마나 물이 채워져있는지는 자기 자신을 루트 노트로 가지는 subtree안에 속한 구간할을 구하면 된다. 따라서 트리의 구간합을 구하는 방식이므로 오일러 투어 테크닉(ETT)를 생각해주면 된다. 따라서 노드 i안에 있는 물의 양은 다음과 같다. $$query[dfs\_in[i], dfs\_out[i]] * depth[i]$$ 이해가 안된다면 다음 블로그 글을 참고하도록 하자. https://thekeykim.github.io/posts/BOJ_18227/ [백준] 18227 - 성대나라의 물탱크 C++ 문제링크 18227 - 성대나라의 물탱크 문제 성대나라에는 각..

Approach 각 세그먼트의 노드에서 가장 최댓값, 그 다음 최댓값을 가지고 있으면 해당 쿼리에서의 최댓값과 그 다음 최댓값을 쉽게 도출할 수 있다. 다만, 2개의 value를 핸들링해야하는 상황이므로 pair도 뭐 가능하긴한데 class를 활용해주었다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; class max_store{ public: int max_1; int max_2; max_store(){ max_1 = -1; max_2 = -1; } max_store(int a){ max_1 = a; max_2 = -1; } max_store(int a, int ..

Approach Subtree에 대한 정보를 가지고 이야기를 하고 있으므로, 오일러 투어 테크닉(ETT)를 활용하면 서브트리에 대한 정보를 쿼리 정보로 바꿔서 처리할 수 있다. 또한 추가적으로 쿼리에 대한 특정 수보다 작거나 크고 k번째 수의 경우는 머지 소트 트리를 활용해서 쉽게 풀 수 있다. 즉, 오일러 투어 테크닉(ETT)와 Mergesort Tree를 활용하면 쉽게 풀 수 있다. 느낌 자체는 https://viyoung.tistory.com/245 [백준 14287번] [세그먼트 트리 / 오일러 투어 테크닉] 회사 문화 3 Approach 가장 원초적으로 생각할 수 있는 풀이는 dfs로 계속 타고 내려가면서 계속 업데이트를 해주면 된다. 다만, 이 경우에는 시간복잡도가 $O(NM)$으로 시간이 초..

Approach 특정 구간에서 k보다 작은 개수/큰 개수는 일반적으로 머지 소트 트리를 활용해서 처리하는 경우가 많다. 머지소트가 진행되는 양상을 잘 살펴보면, 세그먼트가 구성되는 느낌이랑 거의 유사하다. 따라서 어떠한 쿼리에서 k보다 큰 개수를 구하는 과정은 다음과 같다. 1) 원하는 쿼리와 현재 탐색중인 쿼리가 전혀 교차하지 않으면 0 2) 원하는 쿼리가 현재 탐색중인 쿼리를 포함하고 있을 경우, 이진탐색하여 k보다 큰 개수를 구한다. (upper bound) 3) 겹치는 경우에는 재귀적으로 처리하면 1)과 2)의 연산의 합으로 구할 수 있다. k보다 크거나 같은/ 작거나 같은/ 작은의 경우도 비슷한 방식으로 처리해주면 된다. Code #include #define fastio ios_base::sy..

Approach 문제 상황을 보면, 선택한 영화의 등수는 자신보다 더 앞에 놓여진 영화의 개수를 통해 구할 수 있다. 그런데 문제가 되는 상황이 영화를 뽑으면 위치가 가장 앞으로 된다는 것인데, 옮기는 횟수만큼의 추가적인 공간을 확보해주게 되면 원하는 값은 $query[1, x_i] - 1$로 구할 수 있게 된다. 즉, 세그 공간 자체를 $4 * (n + m)$만큼 잡아주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int seg[800000]; void update(int node_index, int node_left, int node_right, int..

Approach 문제를 잘 이해해보면, 현재 자신을 기준으로 자기보다 큰 숫자의 개수 + 1이 자기 등수이다. 이때, 큰 수부터 처리하면서 쿼리를 업데이트하면 이를 구간합으로 바꿔 이해할 수 있다. update하면서 해당 index가 속한 쿼리에 +1씩 시켜주면 된다. 또한, 실력 지표의 범위에 비해서 선수가 압도적으로 적기도 하고 해당 숫자가 너무 크다. 따라서 좌표 압축을 해서 seg의 크기를 줄이도록 하자. 만약 줄이지 해당 점수의 max의 4배를 해야하는데, 당연히 메모리 초과가 난다. 추가적으로 자신의 위치를 처리해야하므로 map을 통해 미리 저장해두도록 하자. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout..

Approach 문제를 잘 보면, cost를 결정하기 위해서는 궁극적으로 나무를 심는 위치를 기반으로 앞에 있는 나무의 개수와 어디에 위치해 있는지 판단하는 것이 중요하다. Let $i$번재 나무 위치를 $x_i$라 하자 그러면, $\text{Cost}_i = \sum\limits_{l \in [L, R], l \neq i} {|x_i - x_l|}$로 나타낼 수 있고, 고등학교 떄 학습한 것처럼 절댓값을 풀면 위 식은 $ \sum\limits_{l \in [L, x_i - 1]} {x_i - x_l} + \sum\limits_{l \in [x_i + 1, R]} {x_l - x_i}$로 나타낼 수 있다. 시그마를 처리해주면 $(n_{f} * x_i - S([L, x_i - 1])) + (S([x_i +..

Approach 잘 생각해보면 쿼리의 시작지점을 기준으로 거리가 홀수, 짝수인 것들을 더해서 비교하는 것인데 애초에 부분합을 2개 따로 관리해주면 된다. 그렇게 되면 문제에서 요구하는 상황을 세그먼트 2개로 풀 수 있다. 사람의 index를 기준으로 홀수면 seg_odd를 업데이트, 짝수면 seg_even을 업데이트 시키고 구간합을 관리해주면 된다. 즉, 예를 들어 query[L, R]이 들어왔다고 하면, 문제에서 구하는 상황은 max(seg_odd[L, R], seg_even[L, R}) - min(seg_odd[L, R], seg_even[L, R])로 구할 수 있다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cou..