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

Approach 문제 상황을 재구성해보면 존재하는 맛 중에 경계값에 위치한 맛을 찾아주면 된다. 상황 자체는 https://viyoung.tistory.com/246 와 근본적으로 동일하다. [백준 19646번] [세그먼트 트리] Random Generator Approach "dp[i] : i번째 수까지 활용했을 때 존재하는 수"라고 잡아서 dp로 풀 수 있을 것처럼 보이지만 이 문제는 업데이트가 자주 나오고 있는 상황이므로, dp 값이 계속 바뀐다. 따라서 이 문제는 dp viyoung.tistory.com 위 문제의 경우는, 경계값을 찾가나가되 업데이트 과정에서 해당 숫자들을 모두 지워주는 형태이다. 반면 이 문제의 경우는 -1을 업데이트 처리해주면 된다. 근본적인 문제의 접근 방법 자체는 완전히 ..

Approach 이 문제의 예시로 제공된 수에서 위치를 가장 판단하기 쉬운 것은 8이다. 왜 8이 가장 마지막 자리에 있는지를 생각해보면 자기보다 작은 수가 한 개도 없고, 가장 큰 숫자이므로 가장 뒤에 오는 것이다. 마찬가지로 7의 경우를 판단해보면 뒤에서부터 남은 자리 중 2개를 건너뛰고 앉으면 된다. 즉, 이를 통해 구간합을 관리하고 있다는 느낌을 받으면 된다. 추가적으로 큰 수부터 작은 수로 자리를 채워나가면서 업데이트 해주면 된다. 다만, 해당 자리가 어딘지를 판단해주기 위해서는 이분탐색으로 파악해주면 된다. 느낌이 https://viyoung.tistory.com/246 와 정말로 비슷하다. 이분탐색을 통해 쿼리의 인덱스를 찾는 느낌이 매우 유사하다. [백준 19646번] [세그먼트 트리] R..

Approach 문제를 풀기 위해서 가장 중요한 것은 출제자의 의도를 읽는 것이다. 어느 범주에서 출제 했는지를 검토해보면, 이 문제는 주어진 쿼리의 최대값을 구하는 문제와 정확하게 동지이다. 추가적으로 범위라고 표현하기는 했지만, 궁극적으로 제시하고 싶은 정보는 쿼리의 길이이다. 슬라이딩 윈도우 기법을 활용해서 가능한 최저부터 최고까지 쭉 쓸고 가면 된다. 시간 복잡도는 $O(NlgN)$정도이므로, 뭐 충분하다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int seg[4000000]; int update(int node_index, int node_left, ..

Approach 다른 기준으로 쿼리를 관리하고 있으므로, Segment tree를 2개 각각 관리해주면 된다. 홀수의 구간합을 seg_odd, 짝수의 구간합을 seg_even에서 관리해주면 된다. 다만, update하는 과정에서 이전의 status가 변경될 수 있기때문에 하위 노드의 값이 바뀜에 따라 해당 index를 포함하고 있는 쿼리를 전부 업데이트 해주어야 한다. 느낌 자체는 구간 곱 쿼리의 처리 방법과 비슷하게 해주면 된다. https://viyoung.tistory.com/248 [백준 11505번] [세그먼트 트리] 구간 곱 구하기 Approach 구간 합 문제랑 비슷하면서도 조금 다르다. 구간 합을 구하는 경우는 update하는 과정에서 하위 노드들의 값을 재참조할 필요가 없이, parame..

Approach 구간 합 문제랑 비슷하면서도 조금 다르다. 구간 합을 구하는 경우는 update하는 과정에서 하위 노드들의 값을 재참조할 필요가 없이, parameter로 주입한 value값을 토대로 갱신만 해주면 된다. 구간 곱의 경우는 0의 존재때문에 다시 갱신해주는 것이 편하다. 잘 생각해보면 update를 할 때, 변한 index를 포함하지 않는 부분은 기존 seg값을 재활용하고 포함하는 경우만 갱신해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef long long ll; ll seg[4000000]; ll update(int node..