BOJ 25925 - 안아줘요

BOJ 25925 - 안아줘요

재미있는 세그먼트 트리 문제이다.

$[X_i-Y_i, X_i+Y_i]$ 의 구간을 고려한다. 어떤 $i$ 에서 갈 수 있는 애들은 $[-\infty, X_i-Y_i]$ 나 $[X_i+Y_i, \infty]$ 에 있는 애들이다.

$Y$가 작은 순서대로 보면서 이 구간에 최대값 쿼리를 날리고, 자신의 DP값을 업데이트 해준다.

좌표압축 + 레이지 세그먼트 트리를 썼다.

아마 레이지 세그먼트 트리를 안쓰고도 $X_i-Y_i$와 $X_i+Y_i$ 에 최대값을 업데이트 해주는것만으로 풀 수 있어보인다.