Approach 이 문제를 보고 파블로프의 개처럼 최댓값과 최솟값을 다루는 문제이므로 우선순위 큐를 생각할 수 있으나 잘 생각해보면 비효율적이라는 것을 쉽게 알 수 있다. 우선순위 큐를 활용한 접근 방법의 가장 큰 문제점은 최대힙과 최소힙이 서로 동기화가 안된다는 것이다. 즉 최대힙을 통해 지운 데이터가 최소합에 반영되기가 힘들다. 이 문제점을 해결하기 위해서 Map이나 Set 등의 자료구조등을 활용해서 지운 데이터인지를 계속해서 비교하는 방법등을 활용할 수 있으나 비효율적이다. 잘 생각해보면 Multiset은 order가 이미 힙트리 상에 저장되어있다. 즉, 이를 활용해주면 하나의 자료구조로 두 개의 값을 동시에 다룰 수 있는 장점이 있다. Codes Priority_queue를 활용한 방법 #incl..

Approach 전체에서 몇 퍼센트 해당하는지를 파악하는 것이므로, 쿼리에 대한 모든 정보를 받고 처리해야 한다. 이 부분에서 오프라인 쿼리 문제임을 인식해주면 된다. 추가적으로 Map container를 활용해주면 해당 set안에 몇 개 들어있는 상황인지를 쉽게 파악할 수 있다. + 어디까지 들어올지 모르는 상황이므로 while(getline(cin, t))를 사용하는 점을 유의깊게 보도록 하자. + cin.precision의 경우 정수부와 소수부의 자리수 개수의 합을 지정해주는 것이다. 소수점 이후의 자리부분을 설정하려면 cout

Approach 이 문제를 물론 네트워크 플로우를 활용해서 풀 수는 있는데, 그리디를 활용한 방법으로 접근해보자. 문제를 정확히 이해해보면, reordering 성질을 만족하는 것을 쉽게 파악할 수 있다. 예를 들어 다음과 같은 행렬이 있다고 하자. $$\begin{pmatrix} 1 &1 & 0 & 1 \\ 1 &0 &1 &1 \\ 1 &1 &1 &1 \\ 1&1 &1 &1 \end{pmatrix}$$ 행과 열의 합을 유지한 상태로 1로 표시된 2개의 element의 위치를 변경할 수 있다. 예를 들어, 첫번째 row vector의 2번째 element대신 3번째 element를 1로 만든 뒤 두번째 row vector의 2번째 element를 1로 만들고 3번째 element를 0으로 만든다. 즉, ..

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..