BOJ 17097

 

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

 

코드

http://boj.kr/a0f7b589826643efb1bcdb0eea351f4b

 

난이도 : P2

 

Elapse Time : 40min

 

예제를 보면서 문제에서 요구하는 사항을 파악했다. 참말쟁이가 $x$명 이상 있으려면 $A_i\leq x\leq B_i$인 $i$가 $x$개 이상 있어야 한다. 이에 따라 모든 $i$에 대해 $A_i$와 $B_i$ 사이에 있는 인덱스에 레이지 세그먼트 트리로 1을 더해놓고 $v[idx]\geq idx$인 최대 $idx$를 찾고자 하였으나 최대 $idx$를 찾는 것에서 막혔다. 레이지 세그먼트 트리를 활용하면 $Q$번의 업데이트도 로그 시간으로 해줄 수 있으므로 최대 $idx$를 찾는 것만 로그 시간안에 해주면 된다. 20분 정도 고민을 하다가 레이지 세그먼트 트리를 만들 때 $v[idx]=-idx$를 넣어놓고 만들면 $v[idx]$가 0 이상인 최대 $idx$를 찾는 문제로 바뀐다는 것을 알게 되었으나 $v[idx]\geq 0$인 최대 $idx$를 찾는 것에서 막혔다. 여기서 세그먼트 트리에서 부모 노드에 정보를 저장할 때 자식 중 최댓값을 저장해놓으면 최댓값이 0 이상인지 여부에 따라 구간 전체에 0이상인 인덱스가 있는지를 판단 가능하다는 것을 깨달았고 이를 통해 문제를 해결했다.