BOJ 31879

https://www.acmicpc.net/problem/31879

 

 

코드

http://boj.kr/c33077594ab64b29afb982119b7f59c9

 

2024 한양대학교 ERICA 프로그래밍 경시대회 HEPC Open Contest N

 

난이도 : P1

 

Elapse Time : 80min

 

문제를 처음 봤을 때 쿼리의 형태부터 살폈다. 문제에서 요구하는 쿼리의 종류는 3개이다. 2번 쿼리는 일반 세그먼트 트리의 update 쿼리와 같고, 3번 쿼리는 금광세그를 조금 변형해주기만 하면 된다. 이 문제가 다른 문제와 가지는 차별점은 1번 쿼리인데, 수열의 값을 바꿔주는 과정에 최대 $N$번 발생할 수 있다. 이 문제를 나이브하게 접근하면 0이 아닌 연속 구간 합을 구하기 위한 1번 세그먼트 트리, 1번 쿼리에서 다음번 인덱스를 찾기 위한 2번 세그먼트 트리 2개의 세그먼트 트리로 해결할 수 있다는 생각이 들었다. 2번 쿼리와 3번 쿼리는 1번 세그먼트 트리만으로 해결이 가능하고 1번 쿼리의 경우 $x>A_i$인 경우 2번 세그먼트 트리로 옮겨가는 인덱스를 찾고 $x=x-A_i$로 만드는 것을 반복해 주면 된다. 처음에는 1번 쿼리가 최악의 경우 $N$번의 연산을 해야 해서 $O(NQ)$의 시간이 걸려 불가능할 것이라고 생각했다. 하지만 1번 쿼리로 인해 $A_i=0$이 된 경우 2번 세그먼트 트리에서 $i$를 리턴하지 않도록 만든다면 모든 1번 쿼리의 시간 복잡도 합이 $O((N+Q)logN)$으로 바운드될 것 같았다. 1번 쿼리로 인해 $A_i=0$으로 바뀌면 다음 1번 쿼리에서는 2번 쿼리로 $A_i>0$이 되기 전까지 등장하지 않을 것이기 때문이다. 이를 통해 1번 쿼리의 시간을 바운드해주었다. 1번 쿼리와 2번 쿼리에서 $A_i$값이 바뀔 때 1번 세그먼트 트리와 2번 세그먼트 트리의 값을 $A_i$가 0이 되거나 0에서 양수가 될 때 잘 바꾸어 주어야 하는데 이 과정에서 실수를 해 몇 번 틀렸고 잘 고쳐서 맞았다.