N coding

모든 q에 대해 a > x && b > y && c > z인 아이가 하나라도 있는지 확인하는 걸 어떻게 빠르게 할수있나 싶어서 한참 고민하다가 질문검색에서 솔루션을 봤는데 세그먼트 트리를 사용하는 새로운 방식(?)을 안 느낌이었다.진짜 다들 똑똑한듯... 우리가 비교해야하는 변수가 3개뿐이어서 가능한 방법인 것 같다. 1. 일단 A와의 거리를 기준으로 정렬해준다. 이러면 앞에 나오는 A가 자신보다 작거나 같다는 것은 확실해진다.2. B와의 거리를 좌표압축을 하여 세그먼트 트리상의 인덱스로 넘긴다.3. C와의 거리는 세그먼트 트리에 저장되는 값이 된다. 4. 이 때 거리가 0 ~ 자신의 거리 - 1 인 인덱스에 있는 애들 중에 MIN값을 추출해왔을 때 자신의 C보다 작다면 자신은 매장을 설치할 수 없는 구..

계속 전함을 segment tree에 넣을 생각만 하고 있어서, 전함을 w 가 큰 거 부터 넣는다.끝나는 지점에 w를 넣고 시작지점-1 에 -w를 넣어서 레이저를 x부터 N까지 합을 구해볼까 등등..근데 이것저것 다 고민해도 삭제가 가장 걸림돌이 되었다. 그러다가 레이저는 기준점이 하나잖아? 라는 생각에서 레이저를 segment tree에 넣으면 모든게 챡챡 풀린다는 것을 깨달았다. 1. 레이저가 x점기준, y점기준으로 들어오니까 각각을 나눠서 세그먼트트리를 2개를 만든다.2. 세그먼트 트리는 좌표를 (좌표압축해야함) 표현하고 있고 안에 들어있는 값은 그 좌표를 뚫는 레이저의 가장 작은 인덱스이다. (가장 먼저나오니까)3. 각각의 전함의 x1 - x2 를 x좌표 세그트리에 넣어서 그 사이를 뚫는 레이저의..