[BOJ] 17513번: Hilbert's Hotel

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

 

대회중에는 풀어내지 못했던 문제입니다. group의 시작 위치를 $ax+b$꼴의 segment tree로 관리하면 1, 2번 쿼리의 처리가 가능하고, 또 group이 추가될 때 마다 유한한 그룹은 묶어서 관리하면 3번 쿼리에 대해 최대 30개의 그룹 묶음을 확인하면 됨을 알 수 있습니다. 그룹 묶음 내에서 정확한 그룹을 찾기 위해서는 binary search를 이용해야 합니다.

 

3번 쿼리의 구현이 개념이 엄청 어려운건 아닌데 이상하게 계속 틀려서 정말 까다로웠습니다.

 

https://github.com/blisstoner/BOJ/blob/master/17513.cpp