루비를 풀었다

 

영롱한 빨간색

 

첫 루비는 꼭 자력솔을 하고 싶어서 하루종일(정확히는 이틀) 잡았다.

6모 직전에 이게 맞는 선택인지는 모르겠다..

총 126번 제출했는데 대부분 별 의미 없는 제출이고 버킷 사이즈 잡았던 게 대부분이다.

Traveling Saga Problem보다 더한 시간 억까를 당해서 fastio랑 비재귀 레이지를 복붙해왔는데 그래서 사실 진짜 자력솔이라 할 수 있는지는 모르겠지만 아무튼 맞았다.

 

풀이를 간단하게만 적자면, 쿼리를 버킷으로 쪼개서, 그 버킷 전체를 포함하는 갱신 쿼리와 포함하지 않는 갱신 쿼리를 나누고 포함하는 경우는 일단 세그로 갱신한 다음 또 홀짝성으로 xor할지 말지를 결정하고, 포함하지 않는 경우는 레이지로 하나하나 업데이트해주면 된다.

위 풀이를 미친듯이 최적화하면 풀린다.

 

이제 시험공부랑 cp나 해야겠다.