백준 16993번과 매우 유사하다. 다만 차이점이 2개 존재한다. 백준 16993번의 경우에는 단순한 금광 세그라면, 이 문제의 경우에는 U와 V를 곱해주는 과정을 수반하게 된다. 추가적으로 이 문제에서는 세그 트리를 중간에 수정함으로써 update과정을 진행해주어야 한다. 일단 처음에 고전했던 부분은 U와 V를 곱해주는 과정을 어떻게 처리할 것인지에 대한 아이디어이다. U의 경우에는 16993번에서 한 결과값에 U만 곱해주면 되는데 V의 경우가 처리하기가 처음에 껄끄러웠다. j - i를 처리해주어야 하기에 처음에는 왼쪽을 기준으로 연산했을 때와 오른쪽을 기준으로 연산했을 때의 갯수를 구조체 안에 넣을 생각을 먼저 했는데 너무 비효율적인 것 같아서 포기하였다. 사실 고민을 좀 해보면, V를 처음 init..

이 문제를 통해 세그먼트 트리의 활용법을 제대로 이해해야 한다. 해당 쿼리의 연속합을 구하는 과정에서 부분 문제들의 partition울 활용할 수 있을 것 같다는 느낌이 직관적으로 매우 강하게 든다. 이 지점에서 Segment Tree 기법을 생각했어야 한다. Segment tree를 처음 init시키는 과정에서 저장한 정보를 활용하여, 주어진 쿼리의 연속합을 도출할 수 있을 것 같은 느낌이 들면 된다. 다만, 문제가 연속합을 도출하기 위해서는 분할정복의 느낌으로 오른쪽과 왼쪽 결과값을 활용해서 도출해주어야하는데 이 과정에서 필요한 정보가 왼쪽을 기준으로 진행했을때의 최대 연속합과 오른쪽으로 진행했을 때의 최대 연속합이다. 또한, 추가적으로 이 모두를 고려했을 때의 최대 연속합이 필요하다. 요약하자면 다..

문제 상황을 이해하려고 끄적거리다보면 숫자를 키워나가면서, 자기보다 앞에 있는 숫자들은 무시한채 채워지지 않은 공간의 갯수를 세면서 자리를 파악하는 것이 핵심이다. 즉, k를 채우기 위해서 1~N까지의 자리 중 1 ~ k - 1번째 숫자가 위치한 곳을 제외하고 앞에서부터 남는 자리의 갯수를 input값이랑 비교해주면 된다. 이 방법으로 문제를 풀려면 다음과 같은 조건이 필요하다. 1. 몇번째 index까지 고려했을 때 주어진 숫자를 만족할 수 있는지 2. 숫자를 채우고나서 위상의 변경을 빠르게 반영할 수 있는지 이 중 2번째 조건에서 세그먼트 트리의 change 함수에서의 역할과 비슷함을 느끼고, 세그먼트 트리로 접근방법을 잡았다. 또한, 몇번째 index까지 고려해야하는지를 생각해야하므로 부분합 구조와..

전형적인 Segment tree 문제이다. 관련한 개녕은 www.crocus.co.kr/648 에 잘 나와있으므로 참고하도록 하자. Init, sum, update함수를 적당히 잘 구현해서 풀어주면 되는 문제이다. 중간중간에 숫자를 수정하고 구간 합을 구하는 지점에서 세그먼트 트리 문제임을 눈치챘어야 한다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); typedef long long ll; using namespace std; ll arr[1000000]; ll tree[1000000 * 4]; ll init(ll start, ll end, ll node){ if(start == end) return tree..